8

iOS アプリの一種のオートコンプリートを実装しています。オートコンプリート値に使用しているデータは、約 100,000 個の文字列を含むカンマ区切りのテキスト ファイルです。これは私が今していることです：

  1. テキスト ファイルを読み取り、NSArray100,000で を作成しますNSString。
  2. ユーザーが入力するときに、[array containsObject:text]

確かに、このルックアップを行うためのより良い/より高速な方法があります。何かご意見は？

4

2 に答える 2

20

絶対、あります！ただし、「Objective-C」ではありません。ほとんどの場合、自分でコーディングする必要があります。

アイデアは、文字列のリストをサフィックスツリーに変換することです。これは、接頭辞で非常に迅速に検索できるデータ構造です。接尾辞ツリーで可能な補完を検索するのは非常に高速ですが、構造自体を構築するのは簡単ではありません。インターネットで簡単に検索したところ、Objective C にはすぐに利用できる実装がないことがわかりましたが、特に時間に追われていなければ、実装を別の言語に移植し たり、C 実装を使用したり、独自の実装を作成したりできる場合があります。

おそらく、文字列をアルファベット順に並べ替え、これまでに入力したプレフィックスに対してバイナリ検索を実行する方が簡単な方法です。接尾辞ツリーほど効率的ではありませんが、17 未満のチェックで適切な場所に到達するため、ソートされた配列アプローチは 100K 文字列に対して許容されます。

于 2012-07-20T20:42:34.573 に答える
2

最も単純なのは、おそらく二分探索です。を参照してください-[NSArray indexOfObject:inSortedRange:options:usingComparator:]。

特に、次のようなことを試してみます。

  • ファイルに保存する配列を事前に並べ替えます
  • おそらく、配列をロードするときに@selector(compare:)（誤ってソートされていないか、いくつかのエッジケースでUnicodeソート順が変更されることが心配な場合）。配列がすでにほとんどソートされていると仮定すると、これはおよそ O(n) になるはずです。
  • 最初の潜在的な一致を見つけるには、[array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
  • エントリにプレフィックスとして searchString が含まれなくなるまで、配列をたどっていきます。おそらく、大文字/小文字/幅を区別しない比較を行って、それがプレフィックスであるかどうかを判断することをお勧めします (NSAnchoredSearch|NSCaseInsensitiveSearch|NSDiacriticInsensitiveSearch|NSWidthInsensitiveSearch)。

これは、すべてのロケール (特にトルコ語) を「正しく」処理しない可能性がありますが、 に置き換えcompare:たりlocalizedCompare:、単純な文字列の折りたたみを行ったりすることはありません。(長さはわずか 9 行ですが、問題を解決するのに約 1 日かかり、約 40 行のコードと 200 行のテストが含まれているため、ここで共有するべきではありません。)

于 2012-07-20T20:59:14.747 に答える