問題タブ [trie]

基本的なプレフィックス ツリーまたは「トライ」を実装しました。トライは次のようなノードで構成されています。

「Apple」、「Ark」、「Cat」という単語をトライに追加するとします。「Ap」や「Ca」などの接頭辞を検索すると、トライの「bool containsPrefix(string prefix)」メソッドが正しく true を返すようになりました。

ここで、"Cat" と "Ark" に対しては true を返しますが、"App" に対しては false を返すメソッド "bool containsWholeWord(string word)" を実装しています (上記の例)。

トライのノードがある種の「endOfWord」フラグを持つのは一般的ですか? これは、検索されている文字列が実際にトライに入力された単語全体であり、単なるプレフィックスではないかどうかを判断するのに役立ちます。

乾杯！

次の形式の文字列を表すための適切なデータ構造を探しています。

• 各「ドメイン」には、次のパターン文字を含めることができます - *, ?( *- 0 文字以上、?- 0 または 1 文字)

• 各「キー」には、次のパターン文字を含めることができます - *, ?( *- 0 文字以上、?- 0 または 1 文字)

• 各「値」には、次のパターン文字を含めることができます - *, ?( *- 0 以上の文字、?- 0 または 1 文字)

例:

JMX ObjectName に精通している場合、基本的にこれは ObjectName パターンです。

各パターンに対応するルールを簡単に保存し、新しいルールをすばやく削除、更新、および追加できる方法を探しています。

私は Prefix Trie を使用することから始めましたが、パターン文字*, ?.

約 600 万の一意の配列を生成する C 関数があります。これらの配列には常にそれぞれ 17 の要素があり、各要素は 0 から 16 までの整数です。また、同じ種類の約 600 万の一意の配列を生成する、その関数のわずかに変更されたバージョンもあります。私の問題は、2 番目の結果が最初の結果よりも約 45,000 少ないことです。これらの結果がどのようなものかを確認したいと思います。

したがって、私のアプローチは、2番目の関数のすべての結果を単純に保存し（電卓は、メモリ内に保持するのに十分な400 mbを超えてはならないことを示しています）、最初の結果を調べて、存在しません。

一般的なアプローチが理にかなっていると仮定すると（そうでない場合は教えてください）、私が探しているのは、約600万の一意の順列を保持できる適切なデータ構造です（理想的にはCで適切に実装されています）

(またはその何らかの変換) を実行し、それらに対して高速メンバーシップ テストを実行します。タイトルが示すように、私はどのデータ構造が機能するかについていくつかの疑いを持っていますが、試行またはハッシュマップがこれに最適な選択であるとは確信していません.

これは、別のアルゴリズムの欠陥を検出するためのアルゴリズムであり、本番環境で使用されるものではありません。私はこれをコード化して人間の言葉で比較的迅速に結果を返す方法でこれを行うことに興味があります.

C# でトライを構築する方法の例をどこで見つけることができるか知っている人はいますか? 辞書/単語のリストを取得して、それを使用してトライを作成しようとしています。

編集 ：

私はあなたの良いアドバイスに従い、トライデータ構造を使用して辞書を含めました。私が選んだ構造は、関心のある人々のためのものです。

しかし、今のところ別の問題があります。アプリケーションを起動するたびにトライ データ構造を構築するのに時間がかかりすぎます。私の辞書が大きすぎるか、選択した trie の実装が単純な辞書には適していない可能性があります。

登録されたデータベースのようにアプリを閉じた後でもこの構造を保存する方法はありますか、または問題が実装によって引き起こされていると思われる場合は、別の方法をお勧めできますか?

Android のプロジェクトで重大な問題が発生しました。

ここでの目標は、一連の 6 文字で作成できるすべての単語を計算することです。

そのために、BDD に 2 つのテーブルがあります。

• '_id' と 'mots' の 2 つの列を持つ 'words'
• 「temp」は同じ列を持つ一時テーブルです。

「words」には語彙のすべての単語が含まれており (非常に大きい)、「temp」には 6 文字 (少なくとも 3 文字を使用) で作成できるすべての可能な文字の組み合わせが含まれています。

テーブル「一時」で実際の単語を選択しようとしているので、テーブル「単語」にある単語を選択しようとしています。これを行うための私のコードは次のとおりです。

良い文字を含む単語の最初の選択を行います (少なくとも 3 文字が使用されます)。

(lettre.tab_char は、一時的に組み合わせを作成するために使用される文字を含む ArrayList(Character) です)

テーブル 'temp2' と 'temp' を結合します。

その後、値をリストビューに入れました。

それは動作しますが、本当に遅いです: 助けてもらえますか?

私はCでスペース効率の良いトライを実装しようとしています。これは私の構造です：

ノードを追加すると、そのインデックスは文字のunsignedcharキャストになります。たとえば、「c」を追加したい場合は、

新しく追加されたノードへのポインタです。ただし、この実装では、256要素のnode*配列を宣言する必要があります。私がやりたいことは：

次に、ノードを追加するときは、ノードのスペースをmallocするだけで、

新しいノードをポイントします。問題は、最初に子供用のスペースをmallocしないと、明らかにインデックスを参照できないか、それ以外の場合は大きなエラーになるということです。

だから私の質問は：それがその子への非nullポインタだけを格納するようにトライを実装するにはどうすればよいですか？

Triesを使用してスペルミスを修正することについてのクールなブログ記事をここで見つけましたが、それは古いバージョンのF＃で書かれていました。
http://blog.lab49.com/archives/2841 問題が発生していると思われるすべての大文字にコメントを付けた最後の部分を除いて、ほとんど修正しました。基本的に、いくつかの場所でセットが期待され、Map <>が与えられ、その逆も同様です。私はこのコードを何時間も見つめていましたが、どこで不一致が発生しているのか理解できないようです。

前もって感謝します、

ボブ

私は、try を使用した文字列マッチングで使用される実際のアルゴリズムについてあまり詳しくありません。

文字列の一致では、接頭辞の試行よりも接尾辞の試行に重点が置かれているように見えるのはなぜだろうか。部分文字列の一致にもプレフィックス試行を使用できませんか? 別の言い方をすれば、プレフィックス試行に対するサフィックス試行の利点は何ですか?

私は現在、Scalaで自分のTrieを実装することに取り組んでおり（学習/趣味の目的で）、それを汎用的に維持しようとしています（文字列だけでなく、反復可能なものをすべて保存できるようにするため）。私のクラスの署名は次のようになります

私はすでにcontains、+ =および-=を実装しています（これはSetの可変バージョンを拡張しています）が、イテレーターに問題があります。私の現在のアプローチでは、優雅な実装を探して頭を悩ませています。すべてのTrieNodeを反復処理し、「有効な終了」としてマークされているものだけを放出する方法があります。そこから、親のリンクをたどって個々のパーツを入手する予定です。（たとえば、ツリーの「hello」は、親'l'->'l'->'e'->'h'を使用して、終了としてマークされた'o'ノードとして格納されます）

今私の問題。私は物事を一般的にしようとしているので、「パーツ」から「アイテム」を再構築する方法がありません。それで、SOの人々への私の質問は、これを処理するための最も優雅な方法は何でしょうか？コンストラクター引数に再構成関数を追加する必要がありますか？Item関数の存在を強制するために、別の方法で境界を設定する必要がありますか？それともまったく別のものですか？