转载请注明出处：http://www.cnblogs.com/kirai/ 作者：Kirai
零.问题的提出
最近希望在分布式平台上实现一个AC自动机，但是如何在这样的分布式平台上表示这样的非线性数据结构就难住我了。因为一直在使用RDD提供的一些基本的操作，没有需要什么复杂的操作。所以突然想到了在分布式的平台上实现一个AC自动机一定很有趣。网上搜了下，发现没有人实现，因此决定尝试实现。或许就是一个玩具，不过也是能帮助自己更深理解分布式平台上进行编程和普通编程的区别吧。
这个问题对我来讲还是有一定的难度的，加上课业、复习考研、竞赛三重压力，对于这个问题的研究时间可能会比较长，不过一定会抽出时间来考虑的。
文章仅仅是在记录自己对问题的思考过程和代码，并不能保证每一步都是合理、有用、正确的。
一.实现可持久化字典树
AC自动机是个什么东西就不赘述了，我首先用python实现了一个比较朴素的版本，这里查询是返回所有字典中出现的单词的起始位置，每一个单词一个list，最终组成一个dict。哈哈，也许有人看出来了这是去年的一道ICPC网赛题，没错。但是我忘记是哪一道了，只记得当时没做出来，所以用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实现JSON转Model - HandyJSON使用讲解
2017-07-26
- 阿里移动安全 Android端恶意锁屏勒索应用分析
2017-07-26
- 集合结合数据结构来看看(二)
2017-07-26
学习是年轻人改变自己的最好方式