Objective-c のあいまい検索マッチングの高速実装を知っている人はいますか? (レーベンシュタイン距離アルゴリズム)。
私はこれを見つけました: https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m - 残念ながらかなり遅いです。これを約 200 個の文字列と比較する必要があります。新しいキーストロークを入力するたびに連続しています。
何か案は？
user429620
質問する
4565 次
2 に答える
10
NSString+Score が希望どおりに機能するが遅すぎる場合は、速度を上げることから始めることができます。の 23 ～ 28 行-scoreAgainst:fuzziness:options:目は、200 回の比較ごとではなく、1 回だけ実行する必要があるセットアップ コードです。そのコードを setup メソッドに取り出して、再度測定します。
編集：
演習として、私はStringScore をフォークし、セットアップ コードを抽出し、最小限の変更を行ってパフォーマンスを改善し、それを測定しました。私は 1000 個のランダムな単語を使用し、それらをそれぞれ 3 つにグループ化しました (例: "disrupted dot Drinking")。これらのグループごとにセットアップを行い（この元の回答で説明したように）、文字列を1000グループすべてと比較しました。私の Core 2 Duo では、これに約 11 秒かかります。
したがって、1 ワードと 1000 ワードを比較するには、約 11 ミリ秒かかります。必要なのは 1 ～ 200 だけなので、おそらく 10 ミリ秒をはるかに下回ります。それはあなたのために働くべきですか？
(ちなみに、まだほぼ半分の時間は rangeOfString に費やされています。つまり、単一の文字を見つけることです。これはおそらくはるかに高速に実行できますが、アルゴリズムの詳細には触れたくありませんでした。)
于 2013-02-21T23:48:33.060 に答える
2
あなたが参照している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" }
于 2013-02-21T22:57:22.970 に答える