標準の挿入メカニズムを使用してプレフィックスツリーを実装しています。アルファベット順に単語のリストが表示されることがわかっている場合、挿入を変更していくつかの手順をスキップする方法はありますか？私はJavaでコーディングしていますが、特定の言語のコードは探していません。各単語のノードをキューに追加し、次の単語のプレフィックスになるまでそれを逆方向にホッピングすることを検討しましたが、これはプレフィックスツリーの全体のポイントを回避している可能性があります。
このようなことについて何か考えはありますか？入力が非常によく似た単語などである場合を除いて、有用な実装を思い付くのは難しいと("aaaaaaaaaab", "aaaaaaaaaac", "aaaaaaaaaad", ...)感じています。ただし、その場合でも、プレフィックスに対して文字列比較を行うことは、通常、プレフィックスツリーを使用する場合と同様のコストになる可能性があります。
ツリーを構築している入力文字列のすべての文字を確認することを避ける方法はありません。これを行う方法があれば、私はあなたのアルゴリズムを間違ったものにする可能性があります。特に、単語wがあり、その文字の1つ（たとえば、k番目の文字）を見ていないとします。次に、アルゴリズムが実行され、単語をトライのどこかに配置しようとすると、すべての文字を知らなくても単語を配置できる必要があります。したがって、単語のk番目の文字を別の文字に変更すると、アルゴリズムによって以前とまったく同じ場所に配置されますが、単語の文字の1つが正しくないため、これは正しくありません。
トライを構築するための通常のアルゴリズムは、入力内の文字数に比例して時間がかかるため、構築コードを並列化する、文字をマシンワードにパックしてヒットするなどのクレイジーなトリックを実行しないと、漸近的にそれを上回ることはできません。あなたのビットハッカリーのハンマーで。
ただし、一定の要素の高速化が得られる可能性があります。リンクされた構造体で多数のポインターを追跡すると、キャッシュのパフォーマンスが低下する可能性があるため、追跡する必要のあるポインターの数を最小限に抑えることで、アルゴリズムを高速化できます。できることの1つは、最後に挿入した文字列の末尾の位置を、ルートまでのパスをトレースするノードのリスト（できれば動的配列として）とともに維持することです。新しい文字を挿入するには、次のようにします。
このように、妥当な長さの共通の接頭辞を持つ単語をたくさん挿入する場合、構造の共有部分を介して大量のポインター追跡を行うことを回避できます。同じプレフィックスを持つ単語がたくさんある場合、これによりパフォーマンスが向上する可能性があります。以前より漸近的に良くはありませんが（実際には、より多くのメモリを使用します）、ポインタに従わないことによる節約は合計される可能性があります。私はこれをテストしていませんが、うまくいくようです。
お役に立てれば！