To answer your questions & some new comments :
1- I would suggest that we create an additional table with alternative spellings.
For example Nine Inch Nails could be also be spelled as Nine Inch or NIN or Trent Reznor could be also linked to Nine Inch Nails
2- a very important detail : all the names should be lower case and also the searched string will have to be automatically converted to lower cases.
3- your idea with taking out common words is indeed ok. So I am thinking that there will be another table with words to be ignored and the system will learn these words.
How? By saving in a separate table ALL the words that are not inside a bands name for example + 1-3 letter words that are in the bands name but they are not relevant. On the admin side of your site you'll be able to pick/validate these special words.
4- the idea with stripping off anything that is not a letter or a digit is also good.
5- in your initial specs you also had "Song" as table, where did that go? :)
6- the algoritm so far would be :
a- make all the entries lower case
b- generate a list of unique words
c- generate one/many table(s) with unique word IDs and their corresponding artist/song/lyric ( here I need more info )
Depending on how exactly the searches will there could be one or many tables with correspondeces.
In your original request you said the searches will be like "artist - song name" : will they always be like this?
Here we need to discuss what you'd want to happen when the artist or song name is not found.
d- create a table with alternative spellings/names for an artist name
e- implement a system based on the actual tables so each artist/song name will have a dynamic "ranking" based on popularity.
f- combine all these tables & also consider the SOUNDEX and have the search algorithm in place :)
If you have played with SOUNDEX you certanly noticed it has some limitations but it also can be very helpful if you find a way of smartly using it.
An example : create an additional table where you save all the searches with UNIQUE index and SOUNDEX and an 0 or 1 for valid or not:
- search_string : unique
- search_string_soundex
- valid : enum(0,1)
Each miss-spelled artist name it has some good chances to have the same SOUNDEX with the real artist name in your database. So when searching for an artist's name and not finding the right name the second step would be to search in the above table for similar soundex and then pick only the entry with the same soundex that has also the "valid" field set to 1.
Now, depending on the user's search behaviour it may make more sense to use the above table first for searching the right artist name or to use the table with unique artist names.
It would be also very useful for me to learn if the users are always searching the artist - song or if they also can search for only artist or song.
Also important for relevancy : on mysubtitles.com each movie name has a rank dinamically updated upon user searches and picks; does your database has something simlar? Because if it doesn't this will have to be added also.