For your site I would plan to use a smart search function that will use exact matches ( the fastest ones ) combined with soundex values ( for automated spelling corrections ) and also with unique keywords indexes.
By unique keywords indexes I mean : to have a separate table like
-id : unique autoincrement ID
-word : unique word
Then another table will hold the corresponding values like :
-id : unique autoincrement ID
- word_id : the id of the word from the above table
- artist_id ( from your Artist table )
- title_id ( from your Song table )
This way the script will VERY quickly ( because it will use UNIQUE indexes combined with unsigned numeric indexes ) be able to locate the songs/artists relevant to the search.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
words
- wordid
- word
- soundex
links
-linkid
-wordid (rather then having word.id and then links.wordid. this way it's same name and easier to follow)
-artistid
-lyricid
Another methods I've picked up that I prefer to use also is taking out too common words such as "the" (that's the only one i take out for now). Additionally some people search for "D.O.H." while it's "DOH" in our database so another thing I do is strip all symbols and characters. (periods, commas, colens, quotes, etc..) which makes it more accurate and easier to find the correct lyrics.
I am interested in seeing how you guys would set the algorithm up and any other methods you would use. The table structure that would be used would be
artists
- artistid
- artist
lyrics
- lyricid
- artistid
- title
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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 :)