實現帶前綴樹的基本搜索引擎

問題是在功能語言中實現前綴樹（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

實現帶前綴樹的基本搜索引擎

回答

相關問題