Levenshtein只有部分字符串的距離（Java）

我有一個在線Web應用程序，帶有頂部菜單樹，用於打開用於執行不同任務的不同小部件。隨着應用程序越來越強大，該樹已變得龐大且難以導航。我實現了一個搜索功能，用戶只需鍵入菜單名稱或其中的一部分，然後使用正則表達式查找菜單樹中與用戶輸入內容相匹配的所有項目。我的正則表達式允許部分單詞和交換單詞，也限制搜索到每個單詞的開頭。它不允許的一件事是拼寫錯誤的單詞。我明白，爲了允許拼寫錯誤的單詞，最好不要使用正則表達式，而是使用字符串距離方法，但我仍然希望允許部分單詞和交換單詞。這可能嗎？Levenshtein只有部分字符串的距離（Java）

例如，如果菜單項是「財務費率維護」，則以下任何一項將與該菜單項匹配：「財務」，「財務報表」，「費率財務」等。比率「不匹配，因爲」inance「不出現在該菜單項的任何單詞的開頭。我想要像「fnane rate」和「rate maintainance」這樣的搜索，它們被拼寫錯誤地匹配。

來源

2010-08-06 Danny Cohn

但「inance率」 ** **是輕微的拼寫錯誤，沒有比「fnane率」更糟糕（非常接近，其實）。爲什麼它不匹配，而後者應該？這是沒有意義的。 – 2010-08-06 19:14:14

因爲它目前的「入場率」不匹配，但我想象一旦實現了字符串距離，它會，但「比率」可能不會因爲字符串距離太大。綁定到單詞開頭的原因是因爲我有類似「vic」的搜索匹配到「地圖服務」，這是不受歡迎的，因爲有很多項目帶有「service」這個詞，但是當用戶搜索「vic」他們通常搜索名爲「VIC」的菜單項 – 2010-08-06 19:19:00

我只是給每個選項添加一個單詞列表，並同時維護一個包含所有單詞的字典。然後，當用戶鍵入他們的查詢時，程序會檢查他們輸入的每個單詞是否在字典中。如果不是，它會通過找到最接近的單詞。字符串距離並更正單詞。

最後，它可能會提示菜單選項的大部分單詞與修正的輸入單詞相同。

拼寫校正（在蟒蛇雖然）的一個很好的例子是在http://norvig.com/spell-correct.html

來源

2010-08-06 19:06:31 hb2pencil

總體思路看起來不錯，但由於權限的緣故，菜單是在登錄時動態生成的，因此我必須在登錄時生成字典並將其存儲在會話中。可以做到，也許是最好的答案，但我希望有更直接的一點 – 2010-08-06 19:20:12

我明白你的意思了，看起來似乎是一個適當的工作來啓動和運行。生成字典和搜索雖然不會在計算上花費太多。 – hb2pencil 2010-08-06 19:27:05

Levenshtein只有部分字符串的距離（Java）

回答

相關問題