轉載請注明出處：http://www.cnblogs.com/kirai/ 作者：Kirai
零.問題的提出
最近希望在分布式平臺上實現(xiàn)一個AC自動機，但是如何在這樣的分布式平臺上表示這樣的非線性數(shù)據(jù)結構就難住我了。因為一直在使用RDD提供的一些基本的操作，沒有需要什么復雜的操作。所以突然想到了在分布式的平臺上實現(xiàn)一個AC自動機一定很有趣。網(wǎng)上搜了下，發(fā)現(xiàn)沒有人實現(xiàn)，因此決定嘗試實現(xiàn)?；蛟S就是一個玩具，不過也是能幫助自己更深理解分布式平臺上進行編程和普通編程的區(qū)別吧。
這個問題對我來講還是有一定的難度的，加上課業(yè)、復習考研、競賽三重壓力，對于這個問題的研究時間可能會比較長，不過一定會抽出時間來考慮的。
文章僅僅是在記錄自己對問題的思考過程和代碼，并不能保證每一步都是合理、有用、正確的。
一.實現(xiàn)可持久化字典樹
AC自動機是個什么東西就不贅述了，我首先用python實現(xiàn)了一個比較樸素的版本，這里查詢是返回所有字典中出現(xiàn)的單詞的起始位置，每一個單詞一個list，最終組成一個dict。哈哈，也許有人看出來了這是去年的一道ICPC網(wǎng)賽題，沒錯。但是我忘記是哪一道了，只記得當時沒做出來，所以用python寫一個就當是對自己的一個補償吧：）
1 # -*- coding: utf-8 -*- 2 class Node: 3 """ 4 A Trie's basic data structure. 5 """ 6 def __init__(self): 7 self.next_letter = {} 8 self.is_word = False 9 self.letter = '' 10 self.depth = -1 11 self.pre = None 12 self.fail = None 13 14 15 class Trie: 16 def __init__(self): 17 self.root = Node() 18 19 20 def insert(self, word): 21 """
延伸閱讀
- ssh框架
2016-09-30
- 阿里移動安全 [無線安全]玩轉無線電——不安全的藍牙鎖
2017-07-26
- 消息隊列NetMQ 原理分析4-Socket、Session、Option和Pipe
2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標分割】
2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞
2017-07-26
- 從棧不平衡問題 理解 calling convention
2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明
2017-07-26
- Swift實現(xiàn)JSON轉Model - HandyJSON使用講解
2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應用分析
2017-07-26
- 集合結合數(shù)據(jù)結構來看看(二)
2017-07-26
學習是年輕人改變自己的最好方式