stringology
Ko-Aluru suffix array construction algorithm
Suffix array是解决string search问题的一个工具，它是一个字串所有后缀的排序。
线性时间的构建算法主要有Kärkkäinen-Sanders()、Ko-Aluru()、KSP三种，其中KSP算法使用了类似suffix tree的构建方式，Kärkkäinen-Sanders算法时间复杂度的递推式为\(T(n)=T(\frac{2n}{3})+O(n)\)，通常认为性能不如\(T(n)=T(\frac{n}{2})+O(n)\)的Ko-Aluru。
按照的注记，借鉴对LMS substring递归排序使用的方法， 对原始的Ko-Aluru算法进行改动以简化内存使用和提升性能。 我的实现在字串和suffix array外仅使用两个数组：计数排序使用的桶和一个表示L/S类型的数组， 反映了Ko-Aluru算法能达到和同等的精简内存占用。
…String index structure: suffix automaton
Suffix automaton
Deterministic acyclic finite state automaton，也叫directed acyclic word graph(DAWG)，是一个识别若干字串的无环DFA。识别若干字串的所有DAWG中，存在唯一一个状态数最少的DAWG，称作minimal DAWG，即识别这个字串集的DFA。
DAWG在有些文献中也指识别一个字串的所有后缀的自动机，这种用法有个更常见的名称：suffix automaton，此时该自动机可以看做是字串所有后缀的DAWG。
…使用Burkhard-Keller tree优化近似串匹配
Approximate string matching
近似字符串匹配问题。
Levenshtein edit distance
在metric space中衡量两个字符串差异程度的一个指标，即通过一系列单字符的编辑操作把字符串A变成字符串B所需的最小编辑次数，其中的编辑操作可以是插入字符、删除字符以及修改字符。
计算编辑距离有个经典的Wagner-Fischer算法，使用了动态规划，用d(i,j)表示把字符串A的前i个字符变成字符串B的前j个字符所需的最小编辑次数（即子串的编辑距离）。
自然语言处理之词语抽取
多日之前看到了Matrix67的《互联网时代的社会语言学：基于SNS的文本数据挖掘》，文中提到的方法是无监管的，而且无需词典就能提取词语，要素概括起来有两点：词的凝聚力，以及左右邻字的信息熵。今天把这个方法实现了一下。
对于凝聚力，我的理解是可以用词前后两部分的pointwise mutual information来描述，比如对于“博物馆”一词，考虑“博”与“物馆”之间，以及“博物”与“馆”之间的pointwise mutual information，两者取较小值作为“博物馆”这个词的凝聚力。