5

问题是在不使用任何存储和迭代方法的情况下用函数式语言实现前缀树（Trie）。

我正在尝试解决这个问题。我应该如何解决这个问题？你能给我确切的算法或链接，显示已经用任何功能语言实现了吗？

为什么我要这样做 => 创建一个具有以下功能的简单搜索引擎

  • 将单词添加到树
  • 在树中搜索单词
  • 删除树中的一个词

为什么我想使用函数式语言 => 我想进一步提高我解决问题的能力。

注意：由于这是我的爱好项目，我将首先实现基本功能。

编辑：

i.）我的意思是“不使用存储”=>我不想使用变量存储（ ex int a ），引用变量 array 。我想通过递归计算结果，然后将结果显示到屏幕上。

ii.) 我写了几行，但后来我删掉了，因为我写的让我生气。很抱歉没有表现出我的努力。

4

2 回答 2

4

看看haskell的Data.IntMap。它是 Patricia trie的纯粹功能实现，它的源代码非常易读。
bytestring-trie包将这种方法扩展到ByteStrings

随附的论文Fast Mergeable Integer Maps也是可读的。它逐步描述了实现：从二进制尝试到大端帕特里夏树。
这是论文的一小部分摘录。

最简单的二叉树是一棵深度等于键中位数的完全二叉树，其中每个叶子要么是空的，表示对应的键是未绑定的，要么是满的，在这种情况下，它包含要对应的键是绑定的。这种风格的 trie 可能在标准 ML 中表示为

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

不可变数据结构实现的关键点是数据和结构的共享。要更新一个对象，您应该使用尽可能多的共享节点创建它的新版本。具体来说，可以使用以下方法进行尝试。

考虑这样一个 trie（来自Wikipedia）：

在此处输入图像描述

想象一下，您还没有添加单词“inn”，但您已经添加了单词“in”。要添加“inn”，您必须创建整个 trie 的新实例，并添加“inn”。但是，您不必强制复制整个内容 - 您只能创建根节点（没有标签）和右班的新实例。新的根节点将指向新的右行，但指向旧的其他分支，因此每次更新时，大部分结构都与前一个状态共享。

但是，您的密钥可能很长，因此每次重新创建整个分支仍然既费时又费空间。为了减轻这种影响，您也可以在一个节点内共享结构。通常每个节点是所有可能结果的向量或映射（例如，在带有标签“te”的图片节点中，有 3 个结果——“a”、“d”和“n”）。不可变映射有很多实现（Scala、Clojure，请参阅它们的存储库以获取更多示例），并且 Clojure 还具有不可变向量（实际上是一棵树）的 出色实现。

所有关于创建、更新和搜索结果尝试的操作都可以递归实现，没有任何可变状态。

于 2012-04-08T09:53:30.183 回答