問題タブ [trie]

トライ データ構造の作成に使用する Python オブジェクトの配列が必要です。タプルのように固定長で、リストのように変更可能な構造が必要です。リストが正確に正しいサイズであることを確認できるようにしたいので、リストを使用したくありません(余分な要素の割り当てを開始すると、トライが大きくなるにつれて、メモリのオーバーヘッドが急速に増加する可能性があります)。これを行う方法はありますか？オブジェクトの配列を作成してみました：

...しかし、それはエラーを出しました:

私がやろうとしていることを行うための最良の方法は何ですか?

クメール語 (単語間にスペースがない言語) 用のオープンソース Java 単語分割プログラムに単語を追加したいと考えています。開発者は長い間それに取り組んでおらず、詳細について連絡することができませんでした (http://sourceforge.net/projects/khmer/files/Khmer%20Word%20Breaking/Khmer%20Word%20Breaking %20program%20V1.0/)。おそらくリストはクメール語辞書から作成されたものであり、より多くの単語を含めるためにファイルを再作成したいと考えています。

単語辞書の形式を特定できる人はいますか (ある種の Trie だと思います)。最初の数行は次のとおりです。

そして、私が新しいものを作成する方法を知っている人はいますか (私は大きな単語リストを持っていますが、それをこの形式にする方法がわかりません)。

ありがとう！

更新3

終わり。以下は、最終的にすべてのテストに合格したコードです。繰り返しになりますが、これはMuriloVasconceloによるSteveHanovのアルゴリズムの修正バージョンをモデルにしています。助けてくれたすべてに感謝します！

更新2

最後に、ほとんどのテストケースでこれを機能させることができました。私の実装は、実際には、MuriloのC++バージョンのSteveHanovのアルゴリズムからの直接翻訳です。では、このアルゴリズムをどのようにリファクタリングしたり、最適化したりする必要がありますか？以下はコードです...

この質問に貢献してくれた皆さん、ありがとうございました。Levenshtein Automataを動作させようとしましたが、実現できませんでした。

したがって、上記のコードに関するリファクタリングや最適化に関する提案を探しています。混乱があれば教えてください。いつものように、必要に応じて残りのソースコードを提供できます。

更新1

そこで、単純なTrieデータ構造を実装し、Steve HanovのPythonチュートリアルに従って、レーベンシュタイン距離を計算しようとしました。実際、私は特定の単語とTrie内の単語の間の最小レーベンシュタイン距離を計算することに興味があるので、 MuriloVasconcelosのバージョンのSteveHanovのアルゴリズムに従っています。うまく機能していませんが、これが私のTrieクラスです。

...およびTrieNodeクラス：

Murilo Vasconcelosが持っているように検索を実装しようとしましたが、何かがおかしいので、これをデバッグするのに助けが必要です。これをリファクタリングする方法や、バグがどこにあるかを指摘する方法について提案してください。最初にリファクタリングしたいのは「minCost」グローバル変数ですが、これは最小のものです。とにかく、ここにコードがあります...

コメントが不足していることをお詫び申し上げます。だから私は何が間違っているのですか？

初期投稿

2つの弦の間のレーベンシュタイン距離を計算する効率的な方法を理解することを期待して、「トライを使用した高速で簡単なレーベンシュタイン距離」という記事を読んでいます。これに関する私の主な目標は、大量の単語セットが与えられた場合に、入力単語とこの単語セットの間の最小レーベンシュタイン距離を見つけることができるようにすることです。

私の簡単な実装では、入力単語ごとに、入力単語と単語のセットの間のレーベンシュタイン距離を計算し、最小値を返します。動作しますが、効率的ではありません...

私はJavaでのTrieの実装を探していましたが、2つの一見良い情報源に出くわしました。

• Koders.comバージョン
• code.google.comバージョン （編集：これはgithub.com/rkapsiに移動したようです）

ただし、これらの実装は、私がやろうとしていることには複雑すぎるようです。それらがどのように機能し、Trieデータ構造が一般的にどのように機能するかを理解するためにそれらを読んでいると、私はさらに混乱するようになりました。

では、Javaで単純なTrieデータ構造を実装するにはどうすればよいでしょうか。私の直感によると、各TrieNodeは、それが表す文字列と、必ずしもすべての文字ではなく、アルファベットの文字への参照を格納する必要があります。私の直感は正しいですか？

それが実装されたら、次のタスクはレーベンシュタイン距離を計算することです。上記の記事のPythonコード例を読みましたが、Pythonについては話せません。再帰検索を実行すると、Java実装のヒープメモリが不足します。では、Trieデータ構造を使用してレーベンシュタイン距離をどのように計算しますか？このソースコードをモデルにした簡単な実装がありますが、Trieを使用していません...非効率的です。

あなたのコメントや提案に加えて、いくつかのコードを見るのは本当に素晴らしいことです。結局のところ、これは私にとっての学習プロセスです...私はTrieを実装したことがありません...したがって、この経験から学ぶことがたくさんあります。

ありがとう。

ps必要に応じて、任意のソースコードを提供できます。また、 Nick Johnsonのブログで提案されているようにBK-Treeを読んで使用してみましたが、思ったほど効率的ではありません...または私の実装が間違っている可能性があります。

この問題に使用するのに最適なデータ構造を見つけようとしています。文字列であるキーを使用してキー値ストアを実装しています。値は頻繁に追加され、通常は1〜2回しか検索されません。最初はstd::map、しかし、キーの追加と赤黒木のリバランスのオーバーヘッドが値を検索する時間の減少を覆い隠していたため、パフォーマンスが最適ではないことがわかりました。現在、変更された単一のリンクリストを使用しています。ac文字列（const char *）、バイト単位の長さ、および格納されている値を含む構造体を使用します。キーを使用して値を検索する場合は、リストを繰り返し処理してキーのサイズを比較します。キーが一致する場合は、memcmpを使用して文字列が同一かどうかを確認します。それらが同一である場合、私は値を返します。この方法を使用すると、の約10倍のパフォーマンスを達成できstd::mapます。ただし、効率を約2倍にする必要があります。この問題に対して、誰かがより良いタイプのデータ構造を推奨できますか？

F# で trie データ構造を実装しようとしています。私はいくつかの問題を抱えています。単語挿入機能をデバッグできません。この関数内のブレークポイントには到達せず、何かがクラッシュしますが、エラーは表示されません。また、私が正しいことを実装したかどうか、私は深刻な疑問を抱いています。とにかくここにコードがあります：

私の質問は次のとおり
です。1. insertWord 関数へのデバッグ アクセスを取得するにはどうすればよいですか? なぜ私は今それを取得していないのですか? エラーが表示されないのはなぜですか?
2. 呼び出しを角かっこ ("[","]") で囲む必要がないように、関数挿入単語が TrieNode オブジェクトのリストを返すようにするにはどうすればよいですか。これはエラーだと思います。
3. このデータ構造を F# に実装する際に、他にアドバイスがあれば歓迎します。私はこの言語に非常に慣れていないので、多くのことを間違っているに違いないことはわかっています。たとえば、リストが空であるかどうかをチェックしないため、単語挿入機能に欠陥があり、途中で終了することを知っています。その橋に着いたら、私はその橋を渡りたかった。

前もって感謝します

前もって感謝します

私はオートコンプリートスクリプトに取り組んでおり、トライの使用を考えていました。私の問題は、一致するすべてのものを返したいということです。たとえば、文字rを入力すると、で始まるすべてのエントリrが返されます。次に、etcで始まるすべてのエントリre。これはトライで実行可能であり、どのように機能しますか。また、もっと良い方法があれば、私は提案を受け入れます。r私が尋ねる理由は、ブランチなどからすべてのノードを返すのは複雑で、多くの処理が必要になるように思われるからです。

はい、私は車輪の再発明をしているかもしれませんが、それがどのように機能するかを学びたいと思います。

すべてのノードの高さを計算するメソッドを使用して、F＃でトライ構造を実装しようとしています。

これは私がこれまでに思いついたものです：

今、私は自分の身長計算関数を書こうとしています。これがバイナリツリーの場合、これは非常に簡単に記述できますが、このツリーには各ノードにサブノードのリストがあるため、F＃で繰り返しトラバースする方法がわかりません。

これは私がこれまでリストフォールド操作を使用して思いついたものですが、コンパイルされません：

この関数を機能させるためにどのように書き直すことができるかについてのアイデアはありますか？または、私の目標を達成するための他の方法についてのアイデアは、これが正しいアイデアではないはずですか？

前もって感謝します

私はaho-corasickアルゴリズムを試して、F＃を少し改善しようとしていますが、Trieの実装で問題が発生しました。これらはすべて変更可能であるか、末尾呼び出しを最適化できません。

私が見ることができる基本的な問題は、不変のデータ構造は、それらが指すものを変更できないため、「ボトムアップ」で構築する必要があるということです。したがって、オプションは、それらを可変にするか、進行中にノードを見つけるかのいずれかです。 （つまり、建設中の再帰）。

構造の末尾呼び出しを最適化して不変のトライデータ構造を作成する方法はありますか？（コピーによって効率が低下しないようにします）。

URL の「最長プレフィックス一致」に使用できる標準の python パッケージに関する情報が必要です。私は2つの標準パッケージhttp://packages.python.org/PyTrie/#pytrie.StringTrie & 'http://pypi.python.org/pypi/trie/0.1.1' を調べましたが、そうではないようですURL の最長プレフィックス マッチ タスクに役立ちます。

たとえば、私のセットにこれらの URL がある場合、1->http://www.google.com/mail 、2->http://www.google.com/document、3->http://www.facebook.comなど。

「http://www.google.com/doc」を検索すると 2 が返され、「http://www.face」を検索すると 3 が返されます。

これを行うのに役立つ標準のpythonパッケージがあるかどうか、またはプレフィックスマッチングのためにTrieを実装する必要があるかどうかを確認したかったのです。

URLの数が増えるにつれて拡張性がないため、正規表現のようなソリューションは探していません。

どうもありがとう。

みんな私は出力を与えるコードを書きました。では、お試しです。今、私は審美的に表示したいと考えています。誰かここで私を助けてください。私の表現は次のようになりますhttp://en.wikipedia.org/wiki/File:Trie_example.svg

しかし、私が欲しいのは、この巨大なモンスターの出力をこの [(1,2), (1,3), (1,4), (3,4)] ???? のようなきれいな出力に変換する方法です。