Java：如何在字符串列表中找到最可能的字符串？

Question

我有一個Java字符串列表，其中包含具有不同拼寫（不完全不同）的人的名字。例如，John可能拼寫爲Jon，Jawn，Jaun等。我應該如何在此列表中檢索最合適的字符串。如果有人能提出一種在這種情況下如何使用Soundex的方法，它應該會有很大的幫助。

Answer 1

你有使用approximate string matching算法，有幾種策略來實現這一點。 Blur是基於Trie的基於Levenshtein字距離的近似字符串匹配Java實現。 you can find the implementation at github here

還有另一種策略來實現其稱爲boyer-moore近似字符串匹配算法。 Here is the Java code for that

使用此算法和Levenshtein字距解決這些問題的常用方法是將輸入與可能的輸出進行比較，並選擇距所需輸出最小距離的輸入。

Answer 2

Solr可以做到這一點，如果您在索引文本的同時使用phonetic filter factory。

是索爾的專業搜索。並搜索相似的聲音詞彙。但是，如果你只是想要這個，而不想要solr提供的其他功能，那麼你可以使用可用的源​​。

Answer 3

有匹配近似串一個jar文件..

經過鏈接並下載frej.jar

http://sourceforge.net/projects/frej/files/

有這個jar文件裏面一個方法

Fuzzy.equals("jon","john"); 

它將在這種類型的近似字符串中返回true。

Answer 4

有很多的理論和方法，估計 2串

給人一種生硬的真/假結果的比賽似乎很奇怪，因爲「喬恩」真不等於「約翰」，它很接近，但沒有按「T匹配

一個偉大的學術工作實施相當多的估計方法被稱爲‘SecondString.jar’ - site link

大多數實現的方法給予一定的分數了比賽，這個分數取決於方法使用

實施例： 允許定義「編輯距離」爲在所需的STR1炭改變的數目來獲得在這種情況下「喬恩」到STR2 - >「john」的要求1個炭此外 自然該方法較低的得分是更好的

Answer 5

本文提供了基於Trie的Java實現的近似字符串匹配的詳細說明和完整代碼： Fast and Easy Levenshtein distance using a Trie。

搜索函數返回的是小於給定

最大從目標字距離的所有字的列表

DEF搜索（字，maxCost）：

# build first row 
currentRow = range(len(word) + 1) 

results = [] 

# recursively search each branch of the trie 
for letter in trie.children: 
    searchRecursive(trie.children[letter], letter, word, currentRow, 
     results, maxCost) 

return results 

這種遞歸上面的搜索功能使用助手。它假定

previousRow已被填充。

DEF searchRecursive（節點，字母，單詞，previousRow，結果，maxCost）：

columns = len(word) + 1 
currentRow = [ previousRow[0] + 1 ] 

# Build one row for the letter, with a column for each letter in the target 
# word, plus one for the empty string at column 0 
for column in xrange(1, columns): 

    insertCost = currentRow[column - 1] + 1 
    deleteCost = previousRow[column] + 1 

    if word[column - 1] != letter: 
     replaceCost = previousRow[ column - 1 ] + 1 
    else:     
     replaceCost = previousRow[ column - 1 ] 

    currentRow.append(min(insertCost, deleteCost, replaceCost)) 

# if the last entry in the row indicates the optimal cost is less than the 
# maximum cost, and there is a word in this trie node, then add it. 
if currentRow[-1] <= maxCost and node.word != None: 
    results.append((node.word, currentRow[-1])) 

# if any entries in the row are less than the maximum cost, then 
# recursively search each branch of the trie 
if min(currentRow) <= maxCost: 
    for letter in node.children: 
     searchRecursive(node.children[letter], letter, word, currentRow, 
      results, maxCost)