实现带前缀树的基本搜索引擎

问题是在功能语言中实现前缀树（Trie）而不使用任何存储和迭代方法。实现带前缀树的基本搜索引擎

我想解决这个问题。我应该如何处理这个问题？你能给我准确的算法或链接哪些显示已经实现了一个在任何功能语言？

为什么我试图做=>创建一个简单的搜索引擎的

加字树
在树
搜索词在树删除一个字的功能

为什么我想用功能性语言=>我想提高我的问题解决能力。

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

编辑：

ⅰ）我的意思是大约“而无需使用存储” =>我不想使用变量存储（例如INT a）中，参照本发明的变量，数组。我想通过递归计算结果然后在屏幕上显示结果。二）我写了一些行，但后来我已经擦除，因为我写的是让我生气。抱歉没有显示我的努力。

来源

2012-04-08 john

“没有使用任何存储”吧？你的意思是没有可变数据？ – 2012-04-08 08:05:47

到目前为止你的努力是什么？ – Bytemain 2012-04-08 08:11:39

它是一个美丽的问题和学习函数式编程的好方法。掌握数据结构和算法和语言的主人将成为你的奴隶。我已经实现了许多种类的树，如三元搜索树，后缀trie等，但在C++中。看到Haskell，Scala或任何其他FP语言如何工作，真是太棒了。 +1 – Yavar 2012-04-08 08:52:19

看看哈斯克尔的Data.IntMap。这是纯粹的功能实现 Patricia trie它的source是非常可读的。
bytestring-trie包扩展这种方法来ByteStrings

有随同纸Fast Mergeable Integer Maps这也是可读的和通过。它逐步描述了实现：从二进制尝试到大端的帕特里夏树。
以下是论文摘要。

在其最简单的，二进制线索是深度等于比特中的键，其中每个叶或者是空数的完整二进制树中，指示相应的键是未结合的，或完整，在的情况下，它包含相应键值为的数据。特里的这种风格可能在标准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-09 11:55:05

嘿，我对功能语言非常熟悉。所以，我不明白源代码是怎么回事。对你而言，它可能是“......非常可读”，而不是我。它在高层完成。你可以切换我或给我算法吗？例如：（对于插入，首先添加;然后...;之后...） – john 2012-04-10 07:02:17

@ user1315050：请指定您想要的内容。您已经对数据结构和操作以及3种编程语言的具体实现给出了高层次的方法描述。你还需要什么？ – ffriend 2012-04-10 08:15:01

@ user1315050，你有没有试过看报纸？我只是从它添加了小提取到我的答案。如果你不明白，那么我在这里没有任何帮助。 – 2012-04-10 12:29:02

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

考虑（从Wikipedia）这样的线索：

enter image description here

试想一下，你有没有附加的单词“旅馆”，但你已经有词“中”。要添加“inn”，你必须创建新的“inn”的实例，添加“inn”。但是，您不必强制复制整个事物 - 只能创建根节点的新实例（不带标签）和正确的banch。新的根节点将指向新的右侧banch，但是到旧的其他分支，因此每次更新时大部分结构都与之前的状态共享。

但是，您的密钥可能相当长，因此每次重新创建整个分支仍然是时间和空间消耗。为了减轻这种影响，您也可以在一个节点内共享结构。通常，每个节点是所有可能结果的向量或映射（例如，在具有标签“te”的图片节点具有3个结果 - “a”，“d”和“n”）。有很多不可变映射的实现（Scala,Clojure，查看它们的存储库以获得更多示例），Clojure也具有优秀的不变矢量implementation（实际上它是一棵树）。

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

来源

2012-04-08 09:53:30 ffriend

实现带前缀树的基本搜索引擎

回答

相关问题