java - 单词的匹配变体（拼写错误，leetspeak）

Question

我需要一个库来匹配单词，给定阈值，拼写错误或其他单词的变体，例如Antoine匹配：

4ntoine
4toine
antoine
4t01n3
titoine
entoine
a n t o i n e

等我该如何解决这个问题？

Answer 1

您也可以按照建议尝试 Levenstein 或 trigram；http://en.m.wikipedia.org/wiki/Trigram_search

Answer 2

您可以尝试使用Jazzy。这最初是由 IBM 开发的，然后似乎没有太多维护。

我不知道今天的状态是什么，但我们成功地用它来做一些接近你想要实现的事情。不过，不确定您是否可以处理 l33t 。

还要检查这个链接

Answer 3

Levenstein 距离可能会有所帮助，但可以首先应用一些启发式规则 AMHO。

请体验以下程序：

public class LevenshteinDistance
{
   public static int computeDistance( String s1, String s2 )
   {
      s1 = s1.toLowerCase();
      s2 = s2.toLowerCase();
      int[] costs = new int[s2.length() + 1];
      for( int i = 0; i <= s1.length(); i++ )
      {
         int lastValue = i;
         for( int j = 0; j <= s2.length(); j++ )
         {
            if( i == 0 ) {
               costs[ j ] = j;
            }
            else
            {
               if( j > 0 )
               {
                  int newValue = costs[ j - 1 ];
                  if( s1.charAt( i - 1 ) != s2.charAt( j - 1 ) ) {
                     newValue =
                        Math.min(
                           Math.min( newValue, lastValue ),
                           costs[ j ] ) + 1;
                  }
                  costs[ j - 1 ] = lastValue;
                  lastValue = newValue;
               }
            }
         }
         if( i > 0 ) {
            costs[ s2.length() ] = lastValue;
         }
      }
      return costs[ s2.length() ];
   }

   public static void main(String[] args) {
      String ref = "Antoine";
      String[] samples = {
         "4ntoine", "4ntoine", "antoine", "4nt01n3", "titoine", "entoine",
         "a n t o i n e" };
      for( String sample : samples ) {
         System.out.printf( "| %s | %-20s | %4d |\n",
            ref, sample, computeDistance( ref, sample ));
      }
   }
}

结果：

| Antoine | 4ntoine              |    1 |
| Antoine | 4ntoine              |    1 |
| Antoine | antoine              |    0 |
| Antoine | 4nt01n3              |    4 |
| Antoine | titoine              |    2 |
| Antoine | entoine              |    1 |
| Antoine | a n t o i n e        |    6 |

如您所见，应预处理最后一个单词以删除空格，并应预处理第四个单词以将 3 替换为 E 并将 4 替换为 A。