How to best rename / move folders?

I badlymessed up my file and folder structure on my audio file hard disk, and only noticed it when all my backups already had the new , bad folder structure...

In the start I had lets say lots of folders in my media library like this:Code:/media/Artist A/CD 1/Title 1.mp3
/media/Artist A/CD 1/Title 2.mp3
...
/media/Artist A/CD 1/Title 3.mp3
/media/Artist A/CD 2/Title 1.mp3
/media/Artist A/CD 2/Title 2.mp3
/media/Artist B/CD 1/Title 1.mp3
...until ...
/media/ZZ_Top/CD 47/Title 18.mp3
/media/ZZ_Top/CD 47/Title 19.mp3So far nothing special, you get it.

Then I decided it would be a good idea to replace all the spaces in file and folder names with underscores (and some other stuff, like Umlauts a ->ae, o->oe, u->ue, ->ss).
For reasons I do not remember this went sideways for some files.

Now I have a mixed-up situation , like this:
Code:/media/Artist A/CD 1/Title 1.mp3
/media/Artist_A/CD 1/Title 2.mp3
...
/media/Artist A/CD 1/Title 3.mp3
/media/Artist_A/CD_2/Title_1.mp3
/media/Artist A/CD 2/Title_2.mp3
/media/Artist B/CD_1/Title 1.mp3
...until ...
/media/ZZ Top/CD_47/Title 18.mp3
/media/ZZ_Top/CD 47/Title_19.mp3Now I have Artist A and Artist_A (with and without underscore) right next to each other in the top level, and about half of the files and folders have underscores in them. SoTechnically all files are still there, nothing is deleted, but dispersed over all permutations of folders (and subfolders!) with underscores or whitespace in their names. So I have the same number of files in roughly twice the folders...

The same, to a lesser extent, is true for the umlaut situation.
I used a modified version of this script: https://gist.github.com/kogakure/34006Code:#!/usr/bin/perl

#===============================================================================
#
# FILE: renametree.pl
#
# USAGE: ./renametree.pl
#
# DESCRIPTION: rename files and directories in the current tree to
# eliminate special characters
#
# OPTIONS: ---
# REQUIREMENTS: ---
# BUGS: ---
# NOTES: ---
# AUTHOR: Felix M. Palmen (fmp), <fmp@palmen.homeip.net>
# COMPANY:
# VERSION: 1.0
# CREATED: 10.09.2008 15:35:57 CEST
# REVISION: ---
#===============================================================================

use strict;
use warnings;

use File::Find ();
use File::Copy ();

my %replacements = (
'[\001-\040]' => '-',
'\_' => '-',
'\,' => '-',
'a' => 'ae',
'\xc3\xa4' => 'ae',
'a\xcc\x88' => 'ae',
'o' => 'oe',
'\xc3\xb6' => 'oe',
'o\xcc\x88' => 'oe',
'u' => 'ue',
'\xc3\xbc' => 'ue',
'u\xcc\x88' => 'ue',
'A' => 'Ae',
'\xc3\x84' => 'Ae',
'A\xcc\x88' => 'Ae',
'O' => 'Oe',
'\xc3\x96' => 'Oe',
'O\xcc\x88' => 'Oe',
'U' => 'Ue',
'\xc3\x9c' => 'Ue',
'U\xcc\x88' => 'Ue',
'' => 'ss',
'\xc3\x9f' => 'ss',
'\&' => 'und',
'\+' => 'und',
'\' => '-Grad',
'\(' => '-',
'\)' => '-',
'\[' => '-',
'\]' => '-',
'\{' => '-',
'\}' => '-',
'\<' => '-',
'\>' => '-',
'\?' => '',
'\!' => '',
'\^' => '',
'\"' => '',
'\' => '',
'\`' => '',
'\#' => '',
'\---' => '-',
'\--' => '-',
);

sub rename
{
my $name = $_;
for (keys(%replacements))
{
$name =~ s/$_/${replacements{$_}}/g;
}
return if ($name eq $_);
if (-e $name)
{
my $i = 0;
++$i while (-e $name.$i);
$name .= $i;
}

print "renaming: '$File::Find::name' => '$name'\n";
File::Copy::move($_, $name);
}

File::Find::finddepth(\&rename, ".");So far, so bad. I should have done more testing.

But now to my attempt to fix the situation (The above script won't help here!):
I tried to find all file and folder names with spaces in them, generate a new filename by converting These spaces to underscores, and finally move(mv) the old file to the new one , depth first.
I took the code fromCode:http://stackoverflow.com/questions/16541582/finding-multiple-files-recursively-and-renaming-in-linuxCode:#!/bin/bash
# rename space to underscore
echo "these exist: "
find . -iname '* *'
for file in $(find . -depth -iname '* *')
do
mv -i $file $(echo "$file" | sed -r 's| |_|g')
done
echo "these still exist:"
find . -iname '* *'I hoped this would "merge" the directories and files together, but this does not work. mv(1) or the underlying filesystem (ext2/3/4) aren't too happy to rename a folder (and mixing its contents) to another existing one with the same name.
I already thought of extracting all files with underscores to another hard disk and then "merging" them via unions, but that would pose its own problems.
Any ideas?