算法问题

TRIE(前缀树/字典树)TRIE常用于存储和表示字符串的集合，并实现该集合上的增删字符串运算。其核心思想是用公共前缀表示字符串，比如abcd与abc的公共前缀是abc，当字符串间恰好没有公共前缀时，比如abc,edfg,czx构成的集合，那么其会存储3个前缀abc,edfg,czx。   其常用于存储字符串构成的集合。其结构是这样的，Trie的根节点不存储字符，其他节点仅存储单个字符，且同一层节点无重复字符。节点有变量存储“颜色”，若某节点被“染色”说明从根到该节点的路径存储了一个字符串，除此之外Trie的叶节点肯定是“染色”的。下面讨论Trie的运算结构： 1）插入：首先查找根节点全部孩子节点，若找到待插入串首字符则进入该节点并重复该步骤，若没有则在该处新建节点并插入剩余字符，最终为叶节点染色。如果用哈希表/dict来记录每个节点的儿子，可以在\(O(1)\)时间完成当前层的查找，所以可以认为时间复杂度为字符数\(O(n)\)。… 阅读全文

单模匹配 字符串是一个序列，序列的每个下标对应一个字符，单模匹配指在字符串A(目标串)中查找字符串B(模式串)，若A中包含B则返回B首次出现时的首字母下标。朴素算法的流程是首先B对齐A首位，然后逐位比较字符，若某位匹配失败则退出，然后将B对齐A的第二位…重复上述步骤。该算法的代价为\(O(ab)\)。 Python def bruteFind(target, pattern): offset = 0 while 1: if offset+len(pattern) > len(target): return -1 for i in range(len(pattern)): if target[i+offset] != pattern[i]: offset += 1 break else: return offset 1234567891011… 阅读全文

多模匹配与AC自动机 多模匹配指“给定单个目标串与多个模式串，确定所有模式串在目标串中的所有出现位置”，相比单模匹配的“单个模式串，首次出现”，多模匹配明显更抽象和复杂（我的看法是AC自动机比KMP难一些）。这里把目标串和模式串分别计为\(t\)和\(p_1,p_2…\)，还是老样子先简单的找一个多模匹配的朴素算法如下。 1）从\(t\)的第1位字符开始，与模式串\(p_1\)逐位对齐比较，匹配成功则记录\(p_1\)在第1位出现1次； 2）从\(t\)的第1位字符开始，与模式串\(p_2\)逐位对齐比较，匹配成功则记录\(p_2\)在第1位出现1次； … n）从\(t\)的第2位字符开始，与模式串\(p_1\)逐位对齐比较，匹配成功则记录\(p_1\)在第2位出现1次； …… 阅读全文

编辑距离模型 给出3种编辑距离模型中对“编辑”操作的定义： 1) Levenshtein距离：允许“替换1个字符、任意位置删1个字符、任意位置插1个字符”，权重都是1； 2) LCS距离(最长公共子序列距离)：允许“任意位置删1个字符、任意位置插1个字符”，权重都是1； 3) Hamming距离：允许“替换1个字符”，权重都是1（两串长度不同时其Hamming距离是无穷）； 所有编辑距离模型对“距离”的定义都是“将\(s_1\)通过模型允许的操作转化为\(s_2\)所耗费的权重”，那么最小编辑距离的定义就是“将\(s_1\)通过模型允许的操作转化为\(s_2\)需要的最小权重”。可以发现“最小编辑距离”是一类定量刻画字符串“相似度”的方案，其通过“编辑复杂程度”刻画“相似度”。 另外，最小编辑距离之所以称为“距离”是因为上述3个模型所定义的最小编辑距离满足数学上距离空间(度量空间)的性质。比如设\(L(s_1,s_2)\)为\(s_1\)到\(s_2\)的最小Levenshtein距离，其满足如下度量空间性质：… 阅读全文