私がここで構築しようとしている特徴は、UIのための用語のダイナミックなリストでtypeahead機能を提供することです.これらの用語は、単語、フレーズ、または数字かもしれません.私は、HTTPリクエストなしで検索操作をすることを望んでいます.そこにはいくつかの解決策がありますが、それらのほとんどは複雑すぎたり、UIコンポーネントとあまり緊密に結合しています.
解決策は次のようになります.
から分離された

検索操作

の効率的な

開発者がフロントエンドまたはバックエンド

のいずれかを実装することができる十分な柔軟性

計画

検索クエリ(接頭辞)を配列に分割する代わりに、配列の形式で、単一の単語、句、および番号に対して比較し、ツリーのデータ構造といくつかの再帰的なアルゴリズムが含まれます.
したがって、3番目の検索木(TST)から始めましょう.各々のノードが文字を含んで、木構造を形成しているエッジによって、接続されるトライトリーの拡張であるTSTは、最大3つの子ノードが含まれているのに対してTestは、より効率的であるのに対して、tryはアルファベットの語彙データセットで最大26の子ノードを含んでいます.

Tries Tree - built with ['search', 'sections', 'seek', 'sear', 'seed', 'set', 'seo']

Ternary Search Tree - built with ['search', 'sections', 'seek', 'sear', 'seed', 'set', 'seo']

TSTデータ構造において、子ノードは、より大きいアルファベットが右に格納されるバイナリ検索木(BST)として記憶される.このようにすることにより,平均値o(log n)の時間的複雑さを持つ探索操作において,反復毎の半分の大きさの問題を軽減することができる.
サブツリーの一方の側が他方の側より2つ以上のエッジを持っている高さバランスの意味でない場合、より悪いケースシナリオでは、私たちは、O(n)の時間複雑さで、葉ノード(木の最後のノード)またはマッチされた接尾辞に到達するまで、探索操作のすべてのノードを打つ必要があります.データセットをランダム化し、ルートノードとしてセットの真ん中にデータ項目を使用することでこれを防ぐことができました.こうすることで、木は平均的に高さをバランスさせることができる.
平均症例
検索- o ( log n )
insert - o ( log n )
最悪の場合:
search - o ( n )
挿入

実装

いくつかの計画の後、私は挿入と検索操作でTSTを実行しているNPM package: typing-aheadをまとめました.
これらの操作は再帰的なアルゴリズムとして書き込まれ、各関数呼び出しが分岐して呼び出しの呼び出しと各呼び出しを作成します.操作をデバッグするために再帰の各ステップにたどり着くことができました.
テストのセット(JESTで書かれた)もTSTが高さをバランスさせて、検索操作が予想された結果を返すことを確実とするためにパッケージに提供されます.テストの1つは妥当なJSONスキーマであることを保証するデータモデルの構造も検証します.
パッケージの動作方法を以下に示します.

モジュールをインポートする

const typeahead = require('typing-ahead');

データセットを供給し、モデルを記録する

const model = typeahead.generate([dataset]);

検索クエリの実行時にモデルを使用する

const results = typeahead.find('queries', model);

npm run test in typing-ahead package runs all available unit tests

ここではどのように動作するかを示すサンドボックスです.
https://codesandbox.io/embed/typing-ahead-pq64e?fontsize=14&hidenavigation=1&theme=dark

結論

一日の終わりには、我々は、開発者のアプリケーションのフロントエンド層のいずれかを実装するか、またはリモート機能を介して検索機能を提供するモジュールの効率的なソリューションをキャッシュしている.

This prototype is built with Jam3 NexJS Generator