問題タブ [trie]

Trieノードにこの構造を使用している人がいるのを見ました。

TREE_WIDTH各配列の長さは必ずしも必要ではないため、効率は低くなります。

それとも私は何かを誤解していますか？

基数ソートの時間計算量はO（kn）です。ここで、nはソートされるキーの数、kはキーの長さです。同様に、トライでの挿入、削除、およびルックアップ操作の時間計算量はO（k）です。ただし、すべての要素が異なると仮定すると、k> = log（n）ではありませんか？もしそうなら、それは基数ソートの漸近的な時間計算量がクイックソートのそれと等しいO（nlogn）であり、トライ操作が平衡二分探索木のそれと等しいO（logn）の時間計算量を持っていることを意味します。もちろん、定数係数は大幅に異なる場合がありますが、漸近的な時間計算量は異なりません。これは本当ですか？もしそうなら、基数ソートと試行には他のアルゴリズムやデータ構造に勝る他の利点がありますか？

編集：

クイックソートとその競合他社はO（nlogn）比較を実行します; 最悪の場合、各比較にはO（k）時間がかかります（キーは最後の桁がチェックされたときにのみ異なります）。したがって、これらのアルゴリズムにはO（knlogn）時間がかかります。同じ論理で、平衡二分探索木操作にはO（klogn）時間がかかります。

ドメイン名のリストがたくさんあり（約6000）、ポートフォリオの大まかな概要として、どの単語が最も高い傾向にあるかを確認したいと思います。

私が抱えている問題は、リストがドメイン名としてフォーマットされていることです。次に例を示します。

examplecartrading.com

examplepensions.co.uk

exampledeals.org

examplesummeroffers.com

+5996

単語数を実行するだけでゴミが発生します。したがって、これを実行する最も簡単な方法は、単語全体の間にスペースを挿入してから単語数を実行することだと思います。

私の正気のために、私はこれをスクリプト化することを好みます。

私は（非常に）小さなPython 2.7を知っていますが、これに取り組む際の推奨事項を受け入れています。コードの例が本当に役立ちます。単純な文字列トライデータ構造を使用することがこれを達成する最も簡単な方法であると言われましたが、Pythonでこれを実装する方法がわかりません。

編集：新しい質問。この質問は当初考えていたよりも難しいと思われるため、NP 複合体の可能性があるため、別の質問があります。使用される文字数の最大化に近づくことができる有用なアルゴリズムは何ですか?

カードゲームの Scrabble Slam に基づいたプログラムを作成することに触発されました! ただし、私はアルゴリズムに慣れていないため、この問題を効率的に解決する方法が思いつきません。

英語で有効な 4 文字の単語を含む文字列から始めます。一度に 1 つの文字をその単語に配置して、その文字を配置することで新しい辞書で有効な単語を形成できます。あなたが持っている文字は、アルファベットの文字と同じです。

たとえば、最初の単語が「カート」だった場合、これは有効な一連の動きである可能性があります。

砂 --> 正気 --> 正弦 --> 線 --> リン --> ピン --> フィン など。

目標は、アルファベットの文字をできるだけ多く (文字を複数回使用せずに) 使用して、シーケンス内の単語の数を最大化することです。

私のアルゴリズムは、最長のシーケンスを見つけることができません。最長のものを推測するだけです。

最初に、開始単語の 1 文字を変更して形成できるすべての単語のリストを取得します。そのリストは「adjacentList」と呼ばれます。次に、adidasList 内のすべての単語を調べて、それらの単語の中で最も隣接する単語がどれかを見つけます。隣接する単語が最も多い単語がどれであっても、開始単語を次の単語に変えることを選択します。

たとえば、sane という単語は 28 の別の単語に変換でき、sine という単語は 27 の別の単語に変換でき、単語 line は別の 30 の単語に変換できます。より多くの単語を綴ることができます。

この問題を解決する最善の方法は何でしょうか? どのようなデータ構造が最適でしょうか? コードを改善して、より効率的で冗長なものにするにはどうすればよいですか?

Tries、ハッシュ、Map（stl）、BSTに関するブログとチュートリアルを読みました。どちらをどこで使うのが良いのか、私は非常に混乱しています。それらはすべて実装に依存しているため、それらの間にそのような違いをもたらすことは意味がないことを私は知っています。より具体的に教えてください。複雑さ（最悪、平均、および最良の場合）についても忘れないでください。

前もって感謝します...

お金を表すフィールドに適切にインデックスを付ける方法についてのガイダンスが必要です。
130.64に一致させるには130が必要です。以下のトライフロート構成を試してみました。

フィールドで130を検索しても、結果が得られません。精度を上げ下げしてみましたが無駄になりました。

番号の一部にインデックスを付けるにはどうすればよいですか？

私はこのトライの実装をocamlに使用しようとしています：http ：//www.lri.fr/~filliatr/ftp/ocaml/ds/trie.ml.html

これは、モジュール「M」の私の実装です。

誤ったセマンティクス（等しい、比較など）を無視します。

私はocamlバッテリーを使用しています、そしてこれは私がこれを機能させる方法です：

このエラーがわかりません。モジュール「M」の実装におけるメソッドのタイプは有効であるように思われます。

また、ocamlがTRIEの実装で必要とされないフィールド（ラベル、中置など）を必要とする理由もわかりません。

メモリにT9辞書があります（trie / hash_map）。辞書には単語評価のペアが含まれているため、辞書から単語が選択されると、その評価が増加し、単語評価のペアが単語リストに表示されます。

辞書から単語を選ぶ方法があるとしましょう。そのメソッドは、いくつかの単語評価ルーチンも実行します。

入力には、電話で押された数字の文字列（1〜9、単語を変更するための「*」および「」）があります。

質問：

1. 文字列を高速に解析するアルゴリズムはありますか？
2. どのデータ構造がそこに適しているでしょうか？

UPD：

問題の全文（問題D）

Hash_mapの実装

実装を試す

私がやろうとしていること:

• ユーザーがスクラブルをプレイするときに再生する単語を見つけるのに役立つモバイル Web アプリケーションを構築する
• ユーザーは、任意の数の文字と 0 個以上のワイルドカードを入力して、単語の候補を表示します

私がこれをやろうとしている方法：

• 40 万語以上を含む辞書で MySQL データベースを使用する
• ASP.NET と C# をサーバー側プログラミング言語として使用する
• HTML5、CSS、Javascript の使用

私の現在の計画:

• データベースのすべての単語を使用して Trie を作成し、ユーザーの文字/ワイルドカード入力に応じて単語をすばやく正確に検索できるようにします

計画を立てても、それを実行できなければ意味がありません。これは私が助けを必要としているものです。

• データベースから Trie を構築するにはどうすればよいですか? (更新: 既にデータベースにある単語を使用して Trie を生成したいのですが、それが完了したら、単語の一致にデータベースを使用するつもりはもうありません)
• 素早く簡単にアクセスできるように Trie を保管するにはどうすればよいですか? （更新：データベースを破棄できるように）
• C# を使用して、文字とワイルドカードに応じてトライを使用して単語を検索するにはどうすればよいですか?

最後に:
どんな助けでも大歓迎です。私はまだ C# と MySQL の初心者なので、優しくしてください

本当にありがとうございました！

初めてトライを使用します。次に通過するブランチを決定する際に、トライに使用するのに最適なデータ構造を知りたいと思いました。配列、ハッシュマップ、リンクリストの中から探していました。