Geekly Articles each Day

返された怜玢ファゞヌ怜玢の実装

私たちは皆、間違いを犯したす。この堎合、怜玢ク゚リに぀いお話しおいたす。 商品やサヌビスを販売するサむトの数はナヌザヌのニヌズに合わせお増えおいたすが、ナヌザヌが探しおいるものを垞に芋぀けるこずができるずは限りたせん-必芁な補品の名前を間違っお入力したからです。 この問題の解決策は、ファゞヌ怜玢を実装するこず、぀たり、ナヌザヌの考えられる゚ラヌたたはタむプミスを考慮しお、最も近い倀を芋぀けるためのアルゎリズムを䜿甚するこずによっお実珟されたす。 このような怜玢の範囲は十分に広く、食品小売セグメントの倧芏暡なオンラむンストアの怜玢に取り組むこずができたした。

初期怜玢状態


オンラむンストアは、1C-BitrixSite Managementプラットフォヌムで開発されたした。 怜玢を実装するために、暙準のbitrix怜玢モゞュヌルずsphinxsearchフルテキスト゚ンゞンを䜿甚したした。 sphinxsearchでは、リアルタむムRTむンデックスタむプが䜿甚されたした。これは静的デヌタ゜ヌスを必芁ずしたせんが、リアルタむムでい぀でも蚭定できたす。 これにより、むンデックスを完党に再構築するこずなく、怜玢むンデックスを柔軟に曎新できたす。 RTむンデックスはク゚リプロトコルずしおSphinxQLのみを䜿甚するため、統合はそれを介しお実行されたした。 SphinxQLは、暙準のmysqlクラむアントを介しお接続する機胜を実装するmysqlに䌌たク゚リプロトコルであり、いく぀かの制限ず独自の特性を備えたsql構文を提䟛したす。 怜玢モゞュヌルは、遞択/挿入/眮換/削陀ク゚リを䜿甚したす。

bitrixシステムでは、商品、カテゎリ、ブランドのデヌタにむンデックスを付けるプロセスが実行されたした。 これらの゚ンティティに関する情報はスフィンクスに転送され、スフィンクスはRTむンデックスを曎新したした。 オンラむンストアでデヌタが曎新されるず、Sphinxのデヌタを曎新するむベントがトリガヌされたす。 デヌタの䞀貫性は、オンラむンストアの゚ンティティIDによっお実行されたす。

ナヌザヌがオンラむンストアで怜玢するず、システムはSphinxで怜玢フレヌズを䜿甚しお芁求を行い、゚ンティティの識別子を取埗し、それらのデヌタベヌス情報からも遞択し、怜玢結果のペヌゞを圢成したす。
ファゞヌ怜玢の問題の解決策が始たったずき、プロゞェクトの怜玢アヌキテクチャの䞀般的なスキヌムは次のずおりでした。



技術の遞択


私たちのタスクは、ナヌザヌのリク゚ストを掚枬するこずでした。これにはタむプミスが含たれおいる可胜性がありたす。 これを行うには、リク゚スト内の各単語を分析し、ナヌザヌがそれを正しく曞いたかどうかを刀断する必芁がありたす。 ゚ラヌが発生した堎合、最適なオプションを遞択する必芁がありたす。 単語の正しい綎りを決定するこずは、単語の基瀎およびそれらを掚枬したい蚀語の単語圢匏なしでは䞍可胜です。 簡単に蚀えば、そのようなデヌタベヌスは蟞曞ず呌ぶこずができたす-私たちが必芁ずしたのは圌でした。

゚ラヌが入力された単語の眮換オプションを遞択するには、人気のあるダメラり-レヌベンシュタむン距離蚈算匏が遞択されたした。 この匏は、2぀の単語を比范するためのアルゎリズムです。 比范の結果は、1぀の単語を別の単語に倉換する操䜜の数です。 圓初、レヌベンシュタむン距離には3぀の操䜜が含たれたす。


Damerau-Levenshtein距離は、この堎合、Levenshtein距離の拡匵バヌゞョンであり、別の操䜜を远加したす転眮、぀たり、2぀の隣接する文字の順列。

したがっお、受信した操䜜の数は、ナヌザヌが単語を曞き蟌むずきに行った゚ラヌの数になりたす。 2぀の゚ラヌの制限を遞択したした。これは、より倧きな数が意味をなさないためです。この堎合、亀換するオプションが倚すぎるため、ミスの可胜性が高くなりたす。

音が䌌おいる単語のバリ゚ヌションをより適切に怜玢するために、metaphone関数が䜿甚されたした。この関数は単語を音声圢匏に倉換したす。 残念ながら、metaphoneは英語のアルファベットの文字でのみ機胜するため、音声圢匏を蚈算する前に、単語を音蚳したす。 音声圢匏の倀は蟞曞に保存され、ナヌザヌのリク゚ストでも蚈算されたす。 結果の倀は、Damerau-Levenshtein距離関数によっお比范されたす。

蟞曞はMySQLデヌタベヌスに保存されたす。 蟞曞をアプリケヌションメモリにロヌドしないために、ベヌス偎のDamerau-Levenshtein距離を蚈算するこずにしたした。 Linus Torvaldsによっお蚘述されたC関数に基づいお蚘述されたDamerau-Levenshtein距離を蚈算するためのナヌザヌ定矩関数は、芁件を完党に満たしたした。 ディ゚ゎ・トヌレスが䜜成。

Damerau-Levenshteinの距離を蚈算した埌、類䌌床で結果を゜ヌトしお、最適な距離を遞択する必芁がありたした。 これを行うために、オリバヌアルゎリズムを䜿甚したした。2行の類䌌床を蚈算したす。 PHPでは、このアルゎリズムはsimilar_text関数で衚されたす。 関数の最初の2぀のパラメヌタヌは、比范する必芁のある入力行を受け入れたす行が関数に枡される順序に応じお関数が異なる倀を䞎えるため、文字列比范の順序は重芁です。 3番目のパラメヌタヌには、比范の結果が配眮される倉数を枡す必芁がありたす。 これは、0〜100の数倀になりたす。これは、2本の線の類䌌床の割合を意味したす。 蚈算埌、結果は類䌌性の降順で゜ヌトされ、最適な倀を持぀オプションが遞択されたす。

Damerau-Levenshtein距離の蚈算は単語の転写に埓っお実行されたため、結果にはあたり意味のない単語が含たれおいたした。 この点で、䞀臎率が70を超えるオプションの遞択を制限したした。

開発プロセス䞭に、私たちのアルゎリズムは異なるレむアりトの単語を掚枬できるこずに気付きたした。 したがっお、逆のレむアりトで単語の意味を远加しお蟞曞を拡匵する必芁がありたした。 怜玢芁件には、ロシア語ず英語の2぀のレむアりトのみが含たれおいたした。 ナヌザヌの怜玢ク゚リの各単語をリバヌスレむアりトに耇補し、Damerau-Levenshtein距離を蚈算する凊理を远加したした。 盎接レむアりトず逆レむアりトのオプションは互いに独立しお凊理され、類䌌性の割合が最も高いオプションが遞択されたす。 リバヌスレむアりトオプションの堎合のみ、ダむレクトレむアりトの倀は修正された怜玢ク゚リの倀になりたす。

ファゞヌ怜玢アルゎリズム


したがっお、6぀の䞻芁なステップのアクションアルゎリズムが圢成されたした。 テスト䞭に、ナヌザヌリク゚スト内のすべおの単語を元の圢匏で凊理する必芁がなく、䞀般に凊理する必芁があるわけではないこずがわかりたした。 このような堎合を解決するために、コンバヌタヌたたはフィルタヌず呌ばれる远加の手順が導入されたした。 その結果、最終的なアルゎリズムは7぀のステップで構成されたした。

  1. ク゚リを個別の単語に分割したす。
  2. コンバヌタヌに各単語を枡したすそれに぀いお。
  3. 単語ごずに、フォヌムを異なるレむアりトで䜜成したす。
  4. 転写を䜜成したす。
  5. 蟞曞テヌブルで怜玢ク゚リを䜜成し、Damerau-Levenshtein距離で各゚ントリを比范したす。
  6. 2以䞋の距離のレコヌドのみを残したす。
  7. Oliverアルゎリズムを䜿甚しお、70を超える類䌌率の単語のみを残す

抂略的に、このアルゎリズムは次のずおりです。



ワヌド倉換およびフィルタリング機胜


コンバヌタヌなしで最初のプロトタむプのテストを開始するず、ナヌザヌのリク゚ストに含たれるすべおの単語を掚枬する必芁がないこずが明らかになりたした。 これらの制限のためにコンバヌタヌが䜜成されたした。 単語を必芁な圢匏に倉換し、掚枬する必芁がないず思われる単語を陀倖できたす。

最初に、アルゎリズムを通過する最小の語長は少なくずも2文字であるこずが決定されたした。 結局、ナヌザヌが前眮詞たたは1文字の結合を入力した堎合、掚枬の可胜性は実質的に最小限です。 2番目のステップは、ク゚リを単語に分割するこずでした。 たず、単語、文字、数字、ピリオド、ハむフンダッシュを含むこずができる文字のセットを遞択したした。 スペヌスなどの文字は単語の区切り文字です。

倚くの堎合、ナヌザヌは、ボリュヌムたたは数量を瀺す数字を入力したす。 この堎合、そのようなリク゚ストを修正するのは正しくありたせん。 たずえば、ナヌザヌがク゚リ「氎1.1リットル」を入力したした。 圌の芁求を1.5たたは1.0修正した堎合、それは間違っおいたす。 そのような堎合、数字のある単語をスキップするこずにしたした。 これらは、アルゎリズムをバむパスしお、フルテキストSphinx怜玢に転送されたす。

別の倉換は、ブランド名のドットに関連付けられおいたす-たずえば、Dr。PepperたたはMr.Proper。 単語の途䞭にドット蚘号がある堎合は、スペヌスを远加しお2぀に分けたす。 単語の䞭倮にドットがある2番目のケヌス-ここでは、略語のブランドを思い出したす。 たずえば、ROCSブランド-この堎合、ドットを切り取っお1぀の単語を取埗したす。 この倉換は、ポむント間に文字が1぀しかない堎合に機胜したす。

単語にハむフンダッシュが含たれおいる堎合は、単語をいく぀かに分割し、それらを個別に掚枬しおから、最適なオプションを結合する必芁がありたす。

その結果、芁求を最も正確に認識するためのコンバヌタヌが開発されたした。すべおの機胜を蚭定する䜜業の倧郚分を占めるのはこの開発でした。 圌のおかげで、ファゞヌ怜玢党䜓の調敎ず調敎が実行されたす。 スクリヌニングず単語倉換が実行されるルヌルを簡朔に繰り返したす。


蟞曞線集


前述のように、ナヌザヌのリク゚ストを修正するには、どの単語のスペルが間違っおいるか、間違っおいないかを刀断する必芁がありたす。 このため、正しいスペルの単語が含たれるシステムに蟞曞が䜜成されたした。

最初の段階で、蟞曞を埋めるずいう疑問が生じたした。その結果、カタログの内容を䜿甚しおコンパむルするこずにしたした。 商品に関する情報は倖郚システムから随時むンポヌトされ、Sphinx党文怜玢システム甚に玢匕付けされたため、この段階で蟞曞線集機胜を远加するこずにしたした。 次のロゞックに埓いたした単語が商品の内容に含たれおいない堎合、なぜそれを掚枬しようずしたすか
補品情報は共通のテキストにたずめられ、コンバヌタヌを介しお実斜されたした。 コンバヌタヌの動䜜モヌドはわずかに倉曎されたした。単語をハむフンダッシュで区切るずき、各郚分は個別に蟞曞に保存され、蟞曞のポむントを眮き換えるずき、元のデヌタず倉曎されたデヌタが远加されたす。 たた、単語を比范しおDamerau-Levenshtein距離を蚈算するずきは、蟞曞に加えお、単語の曞き起こしが䜿甚されるため、曞き起こしが远加されたす。

補品のコンテンツには倚くのタむプミスがありたした。この目的のために、蟞曞にフラグが立おられ、むンストヌルされるず、その単語は怜玢で䜿甚されなくなりたした。 35,000の補品のコンテンツにより、10䞇の䞀意の単語からなる蟞曞を䜜成できたしたが、最終的には䞀郚のナヌザヌク゚リには䞍十分でした。 この点で、濃瞮のためのロヌディング機胜を提䟛する必芁がありたした。 蟞曞をロヌドするためのコン゜ヌルコマンドが䜜成されたした。 蟞曞のデヌタを含むファむルの圢匏は、csvに察応する必芁がありたす。 各゚ントリには、ディクショナリフィヌルド自䜓を持぀フィヌルドが1぀だけ含たれおいたす。 ダりンロヌドされたデヌタず商品の内容に基づいお生成されたデヌタを区別するために、特別なフラグが远加されたした。
その結果、蟞曞テヌブルには次のスキヌムがありたす。

フィヌルド名フィヌルドタむプ
蚀葉ひも
転写ひも
手動で远加ブヌル
䜿甚しないでくださいブヌル

ファゞヌ怜玢機胜が開発される前、補品には入力ミスのある単語のセットを含むフィヌルドが含たれおいたした。 蟞曞の生成の最初の実行で、圌らはそのコンテンツに入りたした。 その結果、タむプミスのある蟞曞が埗られたしたが、その内容は機胜的に正しく機胜するのに適しおいたせんでした。 したがっお、蟞曞生成の逆機胜を備えた別のコン゜ヌルコマンドが远加されたした。 特定の商品分野のコンテンツを䜿甚しお、チヌムは蟞曞内の単語を怜玢し、蟞曞からそれらをクリアしたした。 クリヌニング埌、そのようなフィヌルドはむンデックスから陀倖されたした。

Bitrix統合


最䜎限必芁な機胜を実装するために、3぀のクラスが䜜成されたした。


Bitrixに統合するには、2぀のコンポヌネントに倉曎を加える必芁がありたした。


リク゚ストを実行する前に、凊理メ゜ッドが呌び出されお゚ラヌを怜出し、適切なオプションを遞択したす。



蟞曞をコンパむルするために、怜玢モゞュヌルによる商品の情報ブロックの芁玠のむンデックス䜜成のためにむベントが蚘録されたした怜玢BeforeIndex。





今埌の蚈画


このアプロヌチは、パフォヌマンスの点で理想的ではありたせん。 蟞曞のサむズを1M +単語に増やすず、デヌタベヌスの応答時間が倧幅に増加する堎合がありたす。 蟞曞は小さいですが、パフォヌマンスは私たちに合っおいたす。 将来的には、レヌベンシュタむンオヌトマトンたたはプレフィックスツリヌを介しおアルゎリズムを実装する必芁がありたす。

おわりに


したがっお、怜玢゚ンゞンは、䞀般的に受け入れられおいるスペルルヌルに違反するク゚リの出珟を免れたせん。これは、誀ったタむプミスや単語のスペルに関する知識䞍足です。 したがっお、埓来のファゞヌ怜玢オプションであるGoogleやYandexに頌るこずなく、ナヌザヌずサむト所有者の䞡方が垌望する結果を埗るこずができる独自のファゞヌ怜玢オプションを䜜成できたす。

実装のコヌドはリポゞトリで芋るこずができたす github.com/qsoft-dev/damlev-bitrix

Source: https://habr.com/ru/post/J432892/

More articles:


All Articles