Comparar semelhança entre duas palavras em JAVA

Olá a todos... uma dúvida:

Como comparar "Flávio" == "Flavio" = Verdadeiro? (Comparação independentemente de acento)
Fácil neh, é só procurar letras acentuadas e substituir por não acentuadas!

E para comparar "fLaViO" == "Flavio" = Verdadeiro? (Fácil torna tudo maiúsculo e faz uma comparação normal)

Tudo muito fácil, mas são muitas possibilidades, e tornasse trabalhoso e chato ficar fazendo estas validações.

Muitas vezes queremos comparar semelhança entre dois nomes/palavras, para fazer um validação, onde exista uma margem de erro.

Por exemplo a busca de um cliente. Ex: com o nome Sousa (Soza, Souza, etc)
ou comparação do nome que o funcionário digitou em um sistema comparando com o resultado da digitação de outro sistema. Ex: Um boleto, na geração o usuário digita um nome, no momento do pagamento online, ele informa novamente o nome do sacado, o banco tem que comparar a semelhança neste momento, afinal muitas vezes o usuário digita de forma diferente, faz diferentes abreviações, erra a digitação (tudo que o usuário poder fazer ele fará em sua sede de destruição de sistemas...), e para identificar um erro de pagamento, podemos tolerar cerca 90% se semelhança no nome do secado, isto já seria o suficiente para a transação ocorrer de forma segura.

Hoje em Java não existe qualquer algoritmo pronto para isto, seja da API ou Lib. (O pessoal da Apache bem que podia dar uma tapinha nisto!), então, segue abaixo uma implementação própria, que desenvolvi para um sistema a qual dou manutenção:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.swing.JFrame;
import javax.swing.event.DocumentEvent;
import javax.swing.event.DocumentListener;
import javax.swing.text.AbstractDocument;
import javax.swing.text.AttributeSet;
import javax.swing.text.BadLocationException;
import javax.swing.text.DocumentFilter;

import org.apache.commons.lang.StringUtils;


public class Main extends JFrame{

       private static final long serialVersionUID = 8943714390106983008L;

       private javax.swing.JTextField a;
       private javax.swing.JTextField b;

       public Main() {
               initComponents();
       }

       private void initComponents() {
               java.awt.GridBagConstraints gridBagConstraints;

               a = new javax.swing.JTextField();
               b = new javax.swing.JTextField();

               DocumentFilter filter = new DocumentFilter() {
                       public void insertString(DocumentFilter.FilterBypass fb,
                       int offset, String text, AttributeSet attr)
                       throws BadLocationException {

                               fb.insertString(offset, text.toUpperCase(), attr);
                       }

                       public void replace(DocumentFilter.FilterBypass fb, int offset,
                       int length, String text, AttributeSet attrs)
                       throws BadLocationException {

                               fb.replace(offset, length, text.toUpperCase(), attrs);
                       }
               };
               ((AbstractDocument) a.getDocument()).setDocumentFilter(filter);
               ((AbstractDocument) b.getDocument()).setDocumentFilter(filter);

               a.getDocument().addDocumentListener(new DocumentListener(){
                       public void changedUpdate(DocumentEvent e) {
                               recalcula();
                       }

                       public void insertUpdate(DocumentEvent e) {
                               recalcula();
                       }

                       public void removeUpdate(DocumentEvent e) {
                               recalcula();
                       }

               });

               b.getDocument().addDocumentListener(new DocumentListener(){
                       public void changedUpdate(DocumentEvent e) {
                               recalcula();
                       }

                       public void insertUpdate(DocumentEvent e) {
                               recalcula();
                       }

                       public void removeUpdate(DocumentEvent e) {
                               recalcula();
                       }

               });

               setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
               getContentPane().setLayout(new java.awt.GridBagLayout());

               a.setText("JOAO DE SOUZA");
               gridBagConstraints = new java.awt.GridBagConstraints();
               gridBagConstraints.fill = java.awt.GridBagConstraints.HORIZONTAL;
               gridBagConstraints.ipadx = 10;
               gridBagConstraints.weightx = 10.0;
               gridBagConstraints.insets = new java.awt.Insets(5, 5, 5, 5);
               getContentPane().add(a, gridBagConstraints);

               b.setText("FLAVIO LOPES DE SOUSA");
               gridBagConstraints = new java.awt.GridBagConstraints();
               gridBagConstraints.gridx = 0;
               gridBagConstraints.gridy = 1;
               gridBagConstraints.fill = java.awt.GridBagConstraints.HORIZONTAL;
               gridBagConstraints.ipadx = 10;
               gridBagConstraints.weightx = 10.0;
               gridBagConstraints.insets = new java.awt.Insets(5, 5, 5, 5);
               getContentPane().add(b, gridBagConstraints);

               pack();
       }

       public static void main(String[] args) throws Exception {
               Main m = new Main();
               m.setSize(400, 100);
               m.setDefaultCloseOperation(EXIT_ON_CLOSE);
               m.setVisible(true);
       }

       private void recalcula(){
               this.setTitle(ComparadorSemelhancaEntreNomes.getInstance().compare(a.getText(), b.getText()).toString());
       }

}

class ComparadorSemelhancaEntreNomes {

       private ComparadorSemelhancaEntreNomes () {
       }

       private static ComparadorSemelhancaEntreNomes instance;

       public static ComparadorSemelhancaEntreNomes getInstance (){
               if (instance == null) {
                       instance = new ComparadorSemelhancaEntreNomes();
               }
               return instance;
       }

       /**
       * Implementa o algoritmo de Covington para comparacao de semelhanca entre 2 nomes
       *
       * @param s1 Nome completo 1
       * @param s2 Nome completo 2
       * @return Retorna a porcentagem de semelhanca
       */
       public Double compare(String s1, String s2) {
               if (s1 == null || s2 == null)
               return new Double(0d);

               s1 = preparaPalavraParaEquals(s1);
               s2 = preparaPalavraParaEquals(s2);

               // Se existir abreviações seguidas, tente equalizar
               Pattern pattern = Pattern.compile("(\\w+)\\. (\\w)\\.");
               boolean found;
               do {
                       found = false;
                       Matcher matcher = pattern.matcher(s1); //procura primeiro na s1
                       if (matcher.find()) {
                               if (s2.contains(' ' + matcher.group(1) + matcher.group(2))){
                                       s1 = s1.substring(0, matcher.start() + matcher.group(1).length()) + s1.substring(matcher.start() + matcher.group(1).length() + 2);
                                       found = true;
                               }
                       } else {
                               matcher = pattern.matcher(s2);
                               if (matcher.find()) {
                                       if (s1.contains(' ' + matcher.group(1) + matcher.group(2))){
                                               s2 = s2.substring(0, matcher.start() + matcher.group(1).length()) + s2.substring(matcher.start() + matcher.group(1).length() + 2);
                                               found = true;
                                       }
                               }
                       }
               } while (found);


               // separa palavras em arrays
               String[] tokensS1 = s1.trim().split("\\s+");
               String[] tokensS2 = s2.trim().split("\\s+");

               // coloca a string com mais palavras no primeiro array
               if (tokensS1.length < tokensS2.length) {
                       String[] sTmp = tokensS1;
                       tokensS1 = tokensS2;
                       tokensS2 = sTmp;
               }

               byte salto = 0; //verifica se o assinante pulou algum nome
               double totalPorcentagem = 0;
               for (int i = 0; i < tokensS1.length-salto; i++) {
                       String t2 = tokensS2.length <= i ? "" : tokensS2[i];
                       if (((tokensS1.length - tokensS2.length) > salto) && (tokensS1.length > i+salto+1) && (t2.equals(tokensS1[i+salto+1])))
                       salto++;
                       String t1 = tokensS1[i+salto];

                       if (!"".equals(t2)) {
                               if (t2.charAt(t2.length()-1) == '.') {                            //caso seja uma abreviacao
                                       t1 = t1.substring(0, Math.min(t2.length()-1, t1.length()));   //pega somente a parte de abreviacao para comprar
                                       t2 = t2.substring(0, t2.length()-1);                          //retira o '.'
                               } else if (t1.charAt(t1.length()-1) == '.') {                     //caso seja uma abreviacao
                                       t2 = t2.substring(0, Math.min(t1.length()-1, t2.length()));   //pega somente a parte de abreviacao para comprar
                                       t1 = t1.substring(0, t1.length()-1);                          //retira o '.'
                               }
                       }

                       totalPorcentagem += comparaPalavras(t1, t2);
               }

               return totalPorcentagem / tokensS1.length;
       }

       private String preparaPalavraParaEquals(String s){
               String r = (' ' + s + ' ')
               .toUpperCase()                               //Tudo maiusculo
               .replaceAll(" & ", " E ")
               .replaceAll("\\s*\\.\\s*", ". ")             //converte abreviaçoes(.) para um padrão ". "
               .replaceAll("\\s+", " ")                     //apaga espacos duplicados
               .replaceAll(" M(\\.)? E(\\.)? ", " ME ")     //corrige ME
               .replaceAll(" D[AEIOU](S)? ", " ")           //apaga DA DE DI DO DU DAS DES DIS DOS DUS
               .replaceAll(" [AE] ", " ")                   //apaga A E
               .replaceAll(" AS ", " ")                     //apaga AS
               .replaceAll(" EM ", " ")                     //apaga AS
               .replaceAll("\\s?-\\s?", " ")                //apaga -
               ;
               return r;
       }

       /**
       * Compara um unico nome
       *
       * @param s1 Nome 1 a ser comparado. Nao deve conter espaco
       * @param s2 Nome 2 a ser comparado. Nao deve conter espaco
       * @return Retorna a porcentagem de semalhanca
       */
       private float comparaPalavras(String s1, String s2) {
               // coloca a string com mais palavras no primeiro array
               if (s1.length() < s2.length()) {
                       String sTmp = s1;
                       s1 = s2;
                       s2 = sTmp;
               }

               s2 = StringUtils.rightPad(s2, s1.length(), ' ');

               byte salto = 0; //verifica se o assinante pulou algum caracter
               float acumulador = 0;
               for (int i = 0; i < s1.length()-salto; i++) {
                       if (s1.charAt(i) != s2.charAt(i) && (s1.length() > i+salto+1) && s1.charAt(i+salto+1) == s2.charAt(i)){
                               salto++;
                               acumulador += 30; //penalidade por pular uma letra
                       }
                       acumulador += getPenalidade(s1.charAt(i+salto), s2.charAt(i));
               }

               return ((s1.length() * 100 - acumulador) / s1.length());
       }

       /**
       * Compara um unico caractar
       *
       * @param c1 char 1
       * @param c2 char 2
       * @return retorna a semelhanca
       */
       private int getPenalidade(char c1, char c2) {
               boolean isVogalNome1 = false;
               boolean isConsoanteNome1 = false;
               boolean isVogalNome2 = false;
               boolean isConsoanteNome2 = false;

               // valida sons iguais
               if (isSimilar(c1, c2))
               return 0;

               // Nome 1
               isVogalNome1 = isVogal(c1);
               if (!isVogalNome1)
               isConsoanteNome1 = isConsoante(c1);

               // Nome 2
               isVogalNome2 = isVogal(c2);
               if (!isVogalNome2)
               isConsoanteNome2 = isConsoante(c2);

               // consoantes identicas
               if (isConsoanteNome1 && isConsoanteNome2) {
                       if (c1 == c2)
                       return 0;
                       else
                       return 80;
               }

               // vogais identicas
               if (isVogalNome1 && isVogalNome2) {
                       if (c1 == c2)
                       return 0;
                       else
                       return 50;
               }

               // Termos diferentes
               if ((isVogalNome1 && isConsoanteNome2)
               || (isConsoanteNome1 && isVogalNome2))
               return 100;

               if ((c1 == ' ' && c2 != ' ') || (c1 != ' ' && c2 == ' '))
               return 100;

               return 0;
       }

       /**
       * Checa se os dois caracteres possuem sons semelhantes
       *
       * @param letra1
       * @param letra2
       * @return Retorna true caso sejam
       */
       private boolean isSimilar(char letra1, char letra2) {
               final char[][] matrizEquals = {{'C', 'K'},
                       {'I', 'Y'},
                       {'S', 'Z'},
                       {'W', 'V'}};
               for (char[] cEquals : matrizEquals) {
                       if ((letra1 == cEquals[0] && letra2 == cEquals[1]) ||
                       (letra1 == cEquals[1] && letra2 == cEquals[0]))
                       return true;
               }
               return false;
       }

       /**
       * Checa se o caracter &#233; uma consoante
       *
       * @param letra
       * @return
       */
       private boolean isConsoante(char letra) {
               return "BCDFGHJKLMNPQRSTVWXYZ".contains("" + letra);
       }

       /**
       * Checa se o caracter &#233; uma vogal
       *
       * @param letra
       * @return
       */
       private boolean isVogal(char letra) {
               return "AEIOU".contains("" + letra);
       }

}

Um pre-requisito para o exemplo funcionar é que o jar Apache Commons Lang estejá no classpath(lib) da aplicação.

Este algoritmo é baseado em pontos por comparação de letras e por palavras, seu retorno é a porcentagem de semelhança, entre dois nomes...

Bom, até o proximo ano, até + pessoal...