iOSでのファジーワード検索

良い一日! 今日は、開発者のストーリーを共有したいだけでなく、モバイルデバイス用の標準のファジー検索アルゴリズムを最適化した経験も共有したいと考えています。



背景


それはすべて、スタンフォード大学で「CS193P iOS用アプリを開発する」という講義で始まりました。 しかし、パイロットプロジェクトとして、別の計算機を配布したくありませんでした。 私たちは常に開発のための興味深いアイデアを探していました。 通常起こるように、脳が眠りそうになったときに突然アイデアが生まれました...アイデアは十分に単純でした。アプリケーションは単語のつづり方を決定する必要があります。 また、エラーが発生してユーザーが単語を入力した場合は、正しいスペルを表示します。 このようなアプリケーションは、ジャーナリストや学生を訪問するのに役立ちます(冬のセッションは間近に迫っていました)。 そのようなアプリケーションがないことがわかったとき、私たちは驚きました! はい、せいぜい検索された単語を補完し、1つのタイプミスを許そうとする辞書があります...しかし、検索速度とアプリケーション自体のサイズは落ち込んでいます!

上記のすべてに加えて、Habré記事で説明されているファジー検索アルゴリズムを使用する別のインセンティブがありました 。 このようなアルゴリズムを実装し、モバイルデバイスでの作業の速度を測定することを長い間望んでいました。



はじめに


最初は、検索語が「レーベンシュタイン距離」を使用して辞書の各要素と比較されるときにアプローチが選択されました。 しかし、iPhoneでの「戦闘」条件でのテストでは、このような検索には平均30〜90秒かかることが示されました。これは、辞書にある90,000語にすぎません。 許容できないほど長い! 次に、別の方法が選択されました。最初は、署名によるハッシュ方式を使用して、辞書からインデックスを作成します。 そして、完成したインデックスで単語を探します。 アプリケーションを新しいメソッドにすばやく適合させ、すぐにiPhoneでテストしました。 そして再び失敗-インデックスの作成、それに応じて、アプリケーションの起動には約90〜120秒かかりました。 一部の単語のスペルが正しいかどうかを確認するためにすべてのユーザーが2分間待機するわけではありません。 アプリケーションにはさらに最適化が必要でした。



画像








最適化


次のステップは、Macで辞書インデックスを作成し、完成したインデックスをsqliteデータベースに保存することでした。 次に、iOSデバイスは完成したインデックスを読み込みます。 再度、アプリケーションをリファクタリングし、新しいメソッドに適応させます。 そして最後に、肯定的な結果-7〜12秒でアプリケーションがコールドスタートします。 次に、アプリケーションをさらにロードしようとしました-アプリケーションのボキャブラリーデータベースは355742ワードに拡張されました(ロシア語のいくつかのスペルおよび説明辞書から非常に多くのユニークなワードが収集されました)。 辞書インデックスを更新した後、アプリケーションの起動には10〜15秒かかりました。 しかし、最も重要なことは、類似した単語が多数ある場合、単語検索には数ミリ秒から10秒かかることです。 この結果は私にぴったりでした。 先に進む必要がありました。



追加機能


アプリケーションをより使いやすくするために、いくつかの追加機能を追加しました。

*結果をカテゴリにグループ化:完全一致、単語内の1文字の変更(など-最大3つ)。



画像








*アプリケーションで見つかった単語はすべてクリップボードにコピーできます。

Wiki辞書、Wikipedia、Yandex辞書、およびGoogle検索で単語の意味の検索を追加しました。 ただし、この機能にはインターネット接続が必要です。



画像








*アプリケーションはもともと、ユニバーサルおよび水平および垂直画面モードをサポートするものとして開発されました。



プログラム担当者


アプリケーションの名前を決定した後、アプリケーションは「顔を見つけた」ため、外観に関する議論はなくなりました。 私の目の前には、美しい先生の手書きで大文字が描かれた黒板がありました。 ロシア語の最も一般的なルール、おそらく最も人気のあるルールに追加される文字:文字「and」で「shi」を書く! ほとんどの場合、学校のスペルミスを探して修正する必要があります。 したがって、アプリケーションの名前とデザインにおける学校の雰囲気は、私たちにとって最も適切であるように思われました。



画像








プロジェクトページへのリンク

AppStoreアプリリンク: Ji-Shi



Upd1:

AppStoreの無料アプリへのリンク: Ji-Shi Lite



Upd2:

その後、ユーザーからのフィードバックに基づいて、アプリケーションに次の変更を加えました。



*組み込みの説明辞書(T.F. Efremovaが編集)で検索します。

*ロシア語の現在のルールを追加(スペルチェック)。



建設的な批判、提案、要望をお待ちしています!



PS:習熟のためのプロモーションコード:



N7TMEN3HTPHA

EKRTARHTRYRL

PKYJMERYWMKP

L9TYPNEFA7AH

FETYYTW33TLH

NEN6KFPX74HT

NY7HHLNL4X33

NXHEXR7F3L66

N37F7MTYLN77

9RW9JNYJ43X7

M9FFKK6FTYWA

F69YLWNT4PEN

JWKAELJ3YA7X

R7WMNHW37X94

AHJFRJ3HRAMN

96PTNLTXKJ76

LFPNXNHWA799

WFLENJAMJPK4

HRX6T93W644E

M7YR9T4TTJKL

6HXERELJ7YF7

NJMWP3J6FLLR

M39KYPLFYHE7

7LPAEN4L99KP

YWEP4EPMYM6Y

Y7NWK9ERMHYN

KLHH63HFEWJT

LLKY3PPJ3LLL

WHJFRP63WXRP

FK3WWXJ7MPN9




All Articles