根據字符串列表進行近似搜索

所以是的，我讀了如何在字符串之間使用編輯距離來決定「關閉」是如何彼此串聯的。這個算法作爲一個動態問題實現，需要O（mn）個時間，其中m和n分別是文本和模式的長度。所以如果我必須匹配5000個其他字符串的字符串，它會花費很多時間，這在我的應用程序中是無法接受的。有更快的解決方案可以實施嗎？我不介意交易存儲空間的時間。根據字符串列表進行近似搜索

我在Android上看到一個名爲「Swype」的應用程序，它有類似的功能。它會根據自己的數據庫搜索您的查詢並提供結果。這是如此快速的工作？

注意：請不要建議像Lucene這樣的框架，因爲我不能在J2ME上運行。

來源

2011-06-27 Gooner

這是用於輸入更正嗎？你確定你需要比Levenshtein距離更快的東西嗎？ 5000如果他們是短字典單詞，聽起來不那麼糟糕。 –

這基本上是用於根據預先填充的文章列表來搜索文章名稱（用戶查詢）。現在，由於用戶可能輸入不正確的查詢，所以搜索必須建議最接近的匹配或者如果沒有找到「不匹配」。 – Gooner

splix的回答是好。作爲另一種選擇（非常大的串套），你可能要考慮使用n-gram表現：

http://en.wikipedia.org/wiki/N-gram

這些用於近似的模式匹配在很多數據庫中的包，因爲它們是快速和易於使用傳統的索引方法實現。

來源

2011-06-27 05:53:00 Mikola

我們已經使用http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm幾乎相同的東西，它對我們來說工作得很好。

有它的一些Java實現，你可以找到他們的網站

PS你也可以檢查其他字符串匹配算法：http://en.wikipedia.org/wiki/String_searching_algorithm

來源

2011-06-27 05:50:16

splix，由「我們」是指Swype？ – Gooner

不，我的意思是其他公司，我以前工作過的地方 –

看起來像Aho算法匹配文本的許多關鍵字。在我的情況下，我有一個關鍵字反對很多文字。那麼這個過程是否恰恰相反？也就是說，我現在擁有的所有文字都變成了關鍵詞，而單個關鍵詞變成了文字？ – Gooner

它也是你如何定義「關閉」的問題。如果你不堅持寫作，但口語也可以工作，我可以建議soundex。它是一個非常快速的算法，看看2個單詞是否是一個拼音。

來源

2011-06-27 05:59:14 flolo

我在上述算法的背景下說「close」，但Soundex聽起來確實很酷，但我會看看它 – Gooner

這真的取決於你正在比較的文字。在下面，我將介紹兩種在原始編輯距離框架內加速的方法。

我們曾經有過一個相同的任務，我們將一個短的單詞序列（類似10-30個字符）與一個> 300k短句子（每個10-30個字符）的詞典結合起來。在這種情況下，下面的方法爲我們節省了大量的時間：

排序目標字符串的字典（這必須做一次）
當你建立字符串i可以的N * M個表因爲大多數行都是共同的，所以重用字符串i-1中的表。

例如，如果您有兩個字符串"list of strings"和接下來的"list of words"，您可以重複使用表格的前8行，並且只需重新計算5（這兩個字符串都有8個共同字符）。通過這種方式，我們只需對代碼進行小的更改就可以節省高達70-80％的運行時間。

如果您沒有多長文本，第一種方法並不會節省很多。但在這種情況下，您希望只有少數條目具有較小的編輯距離，而其他所有條目的距離很遠。由於n * m表在每個方向上都有點單調（即每行的最小值是單調的，以及每列），所以一旦達到預先設定的閾值，就可以停止計算。如果在初始閾值內未找到解決方案，則甚至可以保存中間結果並「重新啓動」計算（具有更高的界限）。

來源

2011-06-27 18:00:09 Howard

這些都是一些非常酷的優化我的數據集是按照字典順序排序的，但是我認爲字符串（i-1）的表的重用在很大程度上取決於數據集的類型，我不知道這對我有多大幫助。我打算把閾值保持在一個確定的值，我可能會更好地通過測試各種值（比如哪個值最適合我）來更好地瞭解它們。我會爲您的答案投票，因爲我真的很喜歡錶格概念的重用。 – Gooner

根據字符串列表進行近似搜索

回答

相關問題