Hola, aunque solo trabaje a modo teorico esto de las busquedas de palabras (mas en concreto me refiero a audio, no letras) me acuerdo que uno podria empezar a utilizar arboles de busqueda para lograr mejores métodos de búsqueda. Los arboles basicamente entre mas ramas tiene mayor sera el nivel de precisión de la búsqueda (lo cual hara que encuentre menos resultados) y entre mas general encontrara mas resultados.
Si bien no se como opera el algoritmo de FULL TEXT supongo que se debe basar en alguna manera en algun algoritmo de estos.
Como ves es un poco teorico porque desconozco si a nivel practico en PHP la gente ha desarrollado este tipo de algoritmos. Si alguien conoce sobre el tema que nos pegue una mano, yo tratare de buscar algo mas practico si me queda tiempo.
p.s. He encontrado esto de tipo mas practico. Te tocaria a ti crear las reglas para eliminar prefijos y sufijos de las palabras y apoyarte con sql para refinar tu busqueda. Estoy crudo en el tema porque llevo ya varios años sin trabajarlo. Te tocaria conseguir mas información teórica para lograr arboles con mejores reglas, es algo mas academico.
https://gist.github.com/thinkphp/1448754