data structure

In research papers, a segment tree refers to a tree data structure allowing retrieving a list of segments which contain the given point. In competitive programming, the name "segment tree" usually refers to a data structure maintaining an array. According to http://web.ntnu.edu.tw/~algo/Sequence2.html, the data structure originated from Baltic OI 2001: Mars Maps.

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算法能达到和同等的精简内存占用。

Suffix automaton

Deterministic acyclic finite state automaton，也叫directed acyclic word graph(DAWG)，是一个识别若干字串的无环DFA。识别若干字串的所有DAWG中，存在唯一一个状态数最少的DAWG，称作minimal DAWG，即识别这个字串集的DFA。

DAWG在有些文献中也指识别一个字串的所有后缀的自动机，这种用法有个更常见的名称：suffix automaton，此时该自动机可以看做是字串所有后缀的DAWG。

Proxy auto-config

浏览器的proxy auto-config让我们可以根据URL和host决定使用什么代理。

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，两者取较小值作为“博物馆”这个词的凝聚力。