5

問題は、ストレージと反復メソッドを使用せずに関数型言語でプレフィックス ツリー (Trie) を実装することです。

私はこの問題を解決しようとしています。この問題にどのようにアプローチすればよいですか? 関数型言語で既に実装されている正確なアルゴリズムまたはリンクを教えてください。

私がやろうとしている理由 => の機能を備えた単純な検索エンジンを作成する

  • 単語をツリーに追加する
  • ツリー内の単語を検索する
  • ツリー内の単語を削除する

関数型言語を使いたい理由 ⇒ 問題解決能力をもう少し高めたい。

注 : これは私の趣味のプロジェクトなので、最初に基本的な機能を実装します。

編集：

i.) 「ストレージを使用しない」についての意味 => 変数ストレージ (例 int a )、変数への参照、 array を使用したくない。再帰的に結果を計算し、結果を画面に表示したい。

ii.) いくつかの行を書きましたが、書いたことが腹を立てたので消しました。私の努力を見せなくてごめんなさい。

4

2 に答える 2

4

haskellのを見てくださいData.IntMap。これは、 Patricia trieの純粋関数型実装で あり、そのソースは非常に読みやすくなっています。
bytestring-trieパッケージは、このアプローチをに拡張しますByteStrings

添付の論文FastMergeableInteger Mapsもあり、これも読みやすく、通しやすいものです。実装を段階的に説明します。バイナリ試行からビッグエンディアンのパトリシアツリーまで。
これが紙からの抜粋です。

最も単純なバイナリトライは、キーのビット数に等しい深さの完全なバイナリツリーであり、各リーフは空であり、対応するキーがバインドされていないか、完全であることを示します。この場合、次のデータが含まれます。対応するキーがバインドされています。このスタイルのトライは、StandardMLでは次のように表される場合があります。

datatype 'a Dict =
    Empty
  | Lf of 'a
  | Br of 'a Dict * 'a Dict

バイナリトライで値を検索するには、リーフに到達するまで、指示どおりに左または右に移動して、キーのビットを読み取るだけです。

fun lookup (k, Empty) = NONE
  | lookup (k, Lf x) = SOME x
  | lookup (k, Br (t0,t1)) =
      if even k then lookup (k div 2, t0)
                else lookup (k div 2, t1)
于 2012-04-09T11:55:05.450 に答える
3

不変データ構造の実装における重要な点は、データと構造の両方を共有することです。オブジェクトを更新するには、できるだけ多くの共有ノードを使用して新しいバージョンを作成する必要があります。具体的には、次のアプローチを試してみてください。

そのような試みを考えてみましょう (ウィキペディアから):

ここに画像の説明を入力

"inn" という単語をまだ追加していないが、"in" という単語は既にあると想像してください。「旅館」を追加するには、「旅館」が追加されたトライ全体の新しいインスタンスを作成する必要があります。ただし、すべてをコピーする必要はありません。ルート ノードの新しいインスタンス (ラベルなし) と右のバンチのみを作成できます。新しいルート ノードは新しい右側のブランチを指しますが、古い他のブランチを指すため、更新のたびにほとんどの構造が以前の状態と共有されます。

ただし、キーが非常に長い可能性があるため、ブランチ全体を毎回再作成すると、時間とスペースの両方が消費されます。この影響を軽減するために、1 つのノード内でも構造を共有できます。通常、各ノードは、すべての可能な結果のベクトルまたはマップです (たとえば、「te」というラベルの付いた画像ノードには、「a」、「d」、および「n」の 3 つの結果があります)。不変マップの実装はたくさんあり ( Scala、Clojure、その他の例についてはリポジトリを参照)、Clojureには不変ベクトル (実際にはツリー) の 優れた実装もあります。

結果の試行の作成、更新、および検索に関するすべての操作は、変更可能な状態なしで再帰的に実装できます。

于 2012-04-08T09:53:30.183 に答える