Considerando apenas a implementação do algoritmo tenho uma função adaptada para o MySQL em que os fonemas foram analisados e melhorados conforme o passar do tempo para refletir as buscas realizadas em alguns sistemas. Ele pode conter algumas inconsistências (como no caso do "W" que não tem regra definida), mas resolve a grande maioria dos casos. Os detalhes da implementação estão comentados no decorrer do código:

    DROP FUNCTION IF EXISTS transformar_fonetica;

    DELIMITER $
    CREATE FUNCTION transformar_fonetica(ptexto TEXT)
    RETURNS TEXT
    BEGIN
      DECLARE vtexto             TEXT;
      DECLARE vtexto_apoio       TEXT;
      DECLARE vposicao_atual     INT;
      DECLARE vcaracter_anterior VARCHAR(1);
      DECLARE vcaracter_atual    VARCHAR(1);
      DECLARE vcaracter_seguinte VARCHAR(1);
      DECLARE vsom               VARCHAR(2);
      DECLARE com_acentos        VARCHAR(65);
      DECLARE sem_acentos        VARCHAR(65);

      SET vtexto = UPPER(ptexto);

      SET com_acentos = 'ŠšŽžÀÁÂÃÄÅÆÈÉÊËÌÍÎÏÑÒÓÔÕÖØÙÚÛÜÝŸÞàáâãäåæèéêëìíîïñòóôõöøùúûüýÿþƒ';
      SET sem_acentos = 'SsZzAAAAAAAEEEEIIIINOOOOOOUUUUYYBaaaaaaaeeeeiiiinoooooouuuuyybf';
      SET vposicao_atual = LENGTH(com_acentos);

      -- Remove acentos
      WHILE vposicao_atual > 0 DO
        SET vtexto = REPLACE(vtexto, SUBSTRING(com_acentos, vposicao_atual, 1), SUBSTRING(sem_acentos, vposicao_atual, 1));
        SET vposicao_atual = vposicao_atual - 1;
      end while;

      -- Remove caracteres inválido
      SET vposicao_atual = 1;

      WHILE vposicao_atual <= LENGTH(vtexto) DO
        SET vcaracter_atual = SUBSTRING(vtexto, vposicao_atual, 1);

        IF INSTR('ABCÇDEFGHIJKLMNOPQRSTUVWXYZ ', vcaracter_atual) <> 0 THEN
          SET vtexto_apoio = CONCAT(IFNULL(vtexto_apoio, ''), vcaracter_atual);
        END IF;

        SET vposicao_atual = vposicao_atual + 1;
      END WHILE;

      SET vtexto = vtexto_apoio;

      -- Substitui os mais simples
      SET vtexto = REPLACE(vtexto, 'Ç', 'S');
      SET vtexto = REPLACE(vtexto, 'SH', 'X');
      SET vtexto = REPLACE(vtexto, 'XC', 'S');
      SET vtexto = REPLACE(vtexto, 'QU', 'K');
      SET vtexto = REPLACE(vtexto, 'CH', 'X');
      SET vtexto = REPLACE(vtexto, 'PH', 'F');
      SET vtexto = REPLACE(vtexto, 'LH', 'LI');
      SET vtexto = REPLACE(vtexto, 'NH', 'NI');

      -- Remove duplicados. Menos o S que altera o som da sílaba
      SET vposicao_atual = 1;
      SET vtexto_apoio = '';

      WHILE vposicao_atual <= LENGTH(vtexto) DO
        SET vcaracter_atual = SUBSTRING(vtexto, vposicao_atual, 1);

        IF vposicao_atual < LENGTH(vtexto) THEN
          SET vcaracter_seguinte = SUBSTRING(vtexto, vposicao_atual + 1, 1);
        ELSE -- Último caracter não tem motivo para ser verificado
          SET vcaracter_seguinte = '';
        END IF;

        IF vcaracter_atual <> vcaracter_seguinte OR vcaracter_atual <> 'S' THEN
          SET vtexto_apoio = CONCAT(vtexto_apoio, vcaracter_atual);
        END IF;

        SET vposicao_atual = vposicao_atual + 1;
      END WHILE;

      SET vtexto = vtexto_apoio;

      -- Troca caracteres pelo som
      SET vposicao_atual = 1;
      SET vtexto_apoio = '';

      WHILE vposicao_atual <= LENGTH(vtexto) DO
        SET vcaracter_atual = SUBSTRING(vtexto, vposicao_atual, 1);

        IF vposicao_atual < LENGTH(vtexto) THEN
          SET vcaracter_seguinte = SUBSTRING(vtexto, vposicao_atual + 1, 1);
        ELSE
          SET vcaracter_seguinte = '';
        END IF;

        -- "B" seguindo de qualquer caracter que não seja "A", "E", "I", "O", "U", "R" ou "Y"
        IF vcaracter_atual = 'B' AND INSTR('AEIOURY', vcaracter_seguinte) = 0 THEN
            SET vsom = 'BI';
        -- "C" seguindo de "E", "I" ou "Y"
        ELSEIF vcaracter_atual = 'C' AND INSTR('EIY', vcaracter_seguinte) <> 0 THEN
          SET vsom = 'S';
        ELSEIF vcaracter_atual = 'C' THEN
          SET vsom = 'K';
        ELSEIF vcaracter_atual = 'D'  AND INSTR('AEIOURY', vcaracter_seguinte) = 0 THEN
          SET vsom = 'DI';
        ELSEIF vcaracter_atual = 'G' AND INSTR('EIY', vcaracter_seguinte) <> 0  THEN -- GE, GI OU GY
          SET vsom = 'J';
        ELSEIF vcaracter_atual = 'G' AND vcaracter_seguinte = 'T' THEN -- GT
          SET vsom = '';
        ELSEIF vcaracter_atual = 'H' THEN -- O H é a única letra do nosso alfabeto sem valor fonético, ou seja, sem som.
          SET vsom = '';
        ELSEIF vcaracter_atual = 'N' AND INSTR('AEIOUY', vcaracter_seguinte) = 0 THEN -- Quando for seguida de uma consoante, recebe o som fechado "M"
          SET vsom = 'M';
        ELSEIF vcaracter_atual = 'P' AND INSTR('AEIOURY', vcaracter_seguinte) = 0 THEN
          SET vsom = 'PI';
        ELSEIF vcaracter_atual = 'Q' THEN
          SET vsom = 'K';
        -- QUA, QUE, QUI, QUO ou QUY
        ELSEIF IFNULL(vcaracter_anterior, '') = 'Q' AND vcaracter_atual = 'U' AND INSTR('AEIOY', vcaracter_seguinte) <> 0 THEN
          SET vsom = '';
        -- Quando se localiza entre duas vogais, tem sempre o valor da sonora "Z". Exemplo: Coisa, faisão, mausoléu, lousa, Neusa, Brasil, Sousa, cheiroso, manhoso, gasoso, etc.
        ELSEIF (IFNULL(vcaracter_anterior, '') <> '' AND INSTR('AEIOUY', IFNULL(vcaracter_anterior, '')) <> 0) AND vcaracter_atual = 'S' AND INSTR('AEIOUY', vcaracter_seguinte) <> 0 THEN
          SET vsom = 'Z';
        ELSEIF vcaracter_atual = 'S' AND vcaracter_seguinte = 'C' THEN -- "S" seguido de "C" não tem som
          SET vsom = '';
        ELSEIF vcaracter_atual = 'W' THEN -- O "W" não tem uma regra definida, podendo ser "V" ou "U" dependendo da palavra
          SET vsom = 'V';
        ELSEIF vcaracter_atual = 'X' AND INSTR('AEIOUY', vcaracter_seguinte) <> 0 THEN -- "X "seguido de vogal Exemplo: Exemplo
          SET vsom = 'Z';
        ELSEIF vcaracter_atual = 'X' AND INSTR('AEIOUY', vcaracter_seguinte) = 0 THEN -- "X" seguido de consoante. Exemplo: Exceção
          SET vsom = 'S';
        ELSEIF vcaracter_atual = 'Y' THEN
          SET vsom = 'I';
        ELSEIF vcaracter_atual = 'Z' AND INSTR('AEIOUY', vcaracter_seguinte) = 0 THEN
          SET vsom = 'S';
        ELSE
          SET vsom = vcaracter_atual;
        END IF;

        SET vcaracter_anterior = vcaracter_atual;
        SET vposicao_atual = vposicao_atual + 1;
        SET vtexto_apoio = CONCAT(vtexto_apoio, vsom);
      END WHILE;

      SET vtexto_apoio = REPLACE(vtexto_apoio, 'SS', 'S'); -- Remove o "SS" que foi utilizado para decidir se continuava como "S" ou virava "Z"
      SET vtexto = vtexto_apoio;

      RETURN vtexto;
    END
    $

Algumas saídas de exemplo:

    NEUSA   | NEUZA
    HERESIA | EREZIA
    PALHA   | PALIA
    QUERO   | KERO
    EXIGIR  | EZIJIR
    HESITAR | EZITAR

Algumas com erro de ortografia:

    ÇAPO      | SAPO
    EREZIA    | EREZIA
    ESITAR    | EZITAR
    LAGOZTA   | LAGOSTA
    HORIENTAR | ORIEMTAR

**EDIT**

Revisando as regras resolvi executar um algoritmo parecido mas em **Java**. Percebi que o "X" também não tem uma regra definida, portanto só é possível tratar alguns casos. Adicionei também o tratamento para o _~_. O resultado foi o seguinte:

    import java.text.Normalizer;
    import java.util.LinkedHashSet;

    public class Fonetica {

      public String converterFrase(String frase) {
        LinkedHashSet<String> palavras;
     
        palavras = this.converter(frase.split(" "));
     
        return String.join(" ", palavras);
      }
     
      public LinkedHashSet<String> converter(String... palavras) {
        LinkedHashSet<String> resultado = new LinkedHashSet<>();
     
        for (String palavra : palavras) {
          resultado.add(this.converter(palavra));
        }
     
        return resultado;
      }
     
      public String converter(String palavra) {
        palavra = palavra.toUpperCase();
     
        palavra = palavra.replace("Ç", "SS");
        palavra = palavra.replace("Y", "I");
        palavra = palavra.replace("W", "V"); // "W" não tem uma regra definida, as vezes é "V", as vezes é "U"
        palavra = palavra.replace("GT", "");
        palavra = palavra.replace("Q", "K");
        palavra = palavra.replace("SH", "X");
        palavra = palavra.replace("CH", "X");
        palavra = palavra.replace("PH", "F");
        palavra = palavra.replace("LH", "LI");
        palavra = palavra.replace("NH", "NI");
        palavra = palavra.replace("H", ""); // O "H" é a única letra do nosso alfabeto sem valor fonético.
     
        palavra = this.removerDuplicadas(palavra);
     
        // Acentuações
        palavra = palavra.replaceAll("([ÃÕ])([EO])", "$1-$2"); // Separa as sílabas
        palavra = palavra.replaceAll("([ÃÕ])", "$1M");
        palavra = this.removerAcentos(palavra);
     
        palavra = palavra.replaceAll("([BDP])([^AEIOU]|$)", "$1I$2"); // "B", "D" e "P" mudos
        palavra = palavra.replaceAll("C([AOUR])", "K$1"); // "CA", "CO" e "CU" viram "KA", "KO" e "KU" respectivamente
        palavra = palavra.replaceAll("C([EI])", "SS$1"); // "CE" e "CI" viram "SSE" e "SSI" respecivamente
        palavra = palavra.replaceAll("C([^AEIOU]|$)", "KI$1"); // "C" mudo tem som de "KI"
        palavra = palavra.replaceAll("G([EI])", "J$1"); // "GE" e "GI" tem som de "JE" e "JI" respectivamente
        palavra = palavra.replaceAll("L([^AEIOU]|$)", "U$1"); // Quando o "L" vem antes de consoante
        palavra = palavra.replaceAll("N([^AEIOU]|$)", "M$1"); // Quando "N" for seguida de uma consoante, recebe o som fechado "M"
        palavra = palavra.replaceAll("X([^AEIOU]|$)", "SS$1"); // Quando o "X" é seguido por uma vogal, tem som de "SS"
        palavra = palavra.replaceAll("([AEIOU])S([AEIOU])", "$1Z$2");
        palavra = palavra.replaceAll("Z([^AEIOU]|$)", "SS$1"); // "Z" seguido de vogal tem som de "SS"
     
        palavra = palavra.replaceAll("S+", "S"); // Mais de 1 "S" vira apenas 1
        palavra = palavra.replace("OU", "O"); // Quando o "U" segue o "O" não tem som
     
        return palavra;
      }
     
      private String removerDuplicadas(String texto) {
        String[] letras = "ABCDEFGHIJKLMNOPQRTUVWYXZ".split("");
     
        for (String letra : letras) {
          texto = texto.replaceAll(letra + "+", letra);
        }
     
        return texto;
      }
     
      private String removerAcentos(String texto) {
        texto = Normalizer.normalize(texto, Normalizer.Form.NFD);
        texto = texto.replaceAll("[\\p{InCombiningDiacriticalMarks}]", "");
     
        return texto;
      }
    }

Funcionando no [**IDEONE**](http://ideone.com/6vU6Dk)