Objective-c：快速模糊搜索匹配

有誰知道Objective-c的模糊搜索匹配的快速實現嗎？（levenshtein-distance算法）。Objective-c：快速模糊搜索匹配

我發現這個：https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m - 但它不幸很慢。我需要將它與大約200個字符串進行比較，並且它是連續的 - 每輸入一次新的按鍵。

任何想法？

來源

2013-02-21 Wesley

如果NSString的+分數，你想要做什麼，但速度太慢，你可以通過加速它開始。 -scoreAgainst:fuzziness:options:中的第23至28行是設置代碼，只需執行一次，而不是每次進行200次比較。因此，將該代碼拉出到設置方法中並再次測量。

編輯：

作爲練習，我forked StringScore，提取的設置代碼，做最小的改動來獲得一些性能改進，然後測量它。我用了1000個隨機單詞，每個單詞分成三組（例如「中斷飲酒」）。對於這些組中的每個組，我都進行了設置（如在原始答案中所述），然後將字符串與所有1000個組進行比較。這在我的Core 2 Duo上需要大約11秒。

因此，比較一個單詞到1000大約需要11毫秒。現在你只需要1到200個，所以它可能會低於10毫秒。這應該適合你嗎？

（順便說一句，將近一半的時間花在仍然在rangeOfString：找到一個字符，這大概可以做了很多更快，但我不想在算法的細節來獲得。）

來源

2013-02-21 23:48:33

謝謝，這確實可以大大改善它，但它仍然太慢。 – Wesley 2013-02-22 07:36:32

@韋斯利它讓我感到它對你來說太慢了，所以我測量了它。請參閱修改帖子。 – 2013-02-22 11:15:54

我很抱歉地說，但你是對的。我還有另一位觀察者，同時也是被觸發的罪魁禍首。儘管如此，你的優化是值得的。謝謝！ – Wesley 2013-02-23 09:15:12

我不知道你在Objective-C

參考實現的算法有沒有使用內置的與CoreData NSPredicate的功能的原因。我發現這非常快速搜索超過200個字符串。

例如，給定一個NSString * SEARCHTEXT和fetchedResultsController

NSPredicate * predicate = [NSPredicate predicateWithFormat:@"name CONTAINS[cd] %@", searchText]; 

self.filteredListContents = [[[self fetchedResultsController] fetchedObjects] filteredArrayUsingPredicate:predicate];

你也可以在一個NSArray，我假設你已經嘗試和發現太慢使用NSPredicate。

從蘋果文檔

NSMutableArray *array = 
[NSMutableArray arrayWithObjects:@"Nick", @"Ben", @"Adam", @"Melissa", nil]; 

NSPredicate *bPredicate = [NSPredicate predicateWithFormat:@"SELF beginswith[c] 'a'"]; 

NSArray *beginWithB = [array filteredArrayUsingPredicate:bPredicate]; 
// beginWithB contains { @"Adam" }. 

NSPredicate *sPredicate = [NSPredicate predicateWithFormat:@"SELF contains[c] 'e'"]; 

[array filterUsingPredicate:sPredicate]; 
// array now contains { @"Nick", @"Ben", @"Melissa" }

https://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/Predicates/Articles/pSyntax.html

來源

2013-02-21 22:57:22 Mindeater

謝謝，由於模糊匹配太慢，我正在尋找可以找到包含所有單詞的匹配項的內容。所以，如果我正在尋找「堆棧溢出」，匹配的對象將是「堆棧溢出」和「溢出堆棧」。我想這可以用NSPredicate來完成，如果我分開所有單詞並單獨爲每個單詞嘗試它。我會試一試。 – Wesley 2013-02-22 07:13:20

@韋斯利，但這只是[NSSet setWithArray：[string componentsSeparatedByString：@「」] isEqual：otherSet] – 2013-02-22 09:07:20

@wm嗯，不完全是，它也應該匹配「溢出匹配堆棧」等。無論如何，看起來像我有對每個單詞執行正則表達式搜索或對每個單詞執行謂詞搜索。 – Wesley 2013-02-22 09:23:40

Objective-c：快速模糊搜索匹配

回答

相關問題