Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus
Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in a Corpus
复制标题
DOI：
10.1162/089120101300346787
复制
发表时间：
2001-03
影响因子：
9.3
通讯作者：
Mikio Yamamoto;Kenneth Ward Church
中科院分区：
文献类型：
--
作者：
Mikio Yamamoto;Kenneth Ward Church
二元组和三元组常用于统计自然语言处理；本文将描述处理更长的 n 元语法的技术。后缀数组（Manber 和 Myers 1990）首次被引入来计算长度为 N 的序列（语料库）中子串（n-gram）的频率和位置。为了计算语料库中所有 N(N+1)/2 个子串的频率，子串被分组为可管理数量的等价类。通过这种方式，对子串的禁止性计算被减少为对类的可管理计算。本文介绍了用于计算两个大型语料库（包含 5000 万单词的《华尔街日报》英语语料库和包含 2.16 亿字符的《每日新闻》日语语料库）中所有 n 元语法的词频 (tf) 和文档频率 (df) 的算法和代码。论文的后半部分使用这些频率来寻找有趣的子串。词典编纂者一直对具有高互信息 (MI) 的 n 元语法感兴趣，其中联合术语频率高于偶然预期的频率（假设 n 元语法的各部分独立组合）。剩余逆文档频率 (RIDF) 将文档频率与另一种机会模型进行比较，其中具有特定术语频率的术语在整个集合中随机分布。 MI 倾向于挑选具有非组合语义的短语（这通常违反独立性假设），而 RIDF 倾向于突出技术术语、名称和用于信息检索的良好关键字（它们倾向于在文档中表现出非随机分布）。在日语单词提取任务中，MI 和 RIDF 的组合比单独使用两者效果更好。
Bigrams and trigrams are commonly used in statistical natural language processing; this paper will describe techniques for working with much longer n-grams. Suffix arrays (Manber and Myers 1990) were first introduced to compute the frequency and location of a substring (n-gram) in a sequence (corpus) of length N. To compute frequencies over all N(N+1)/2 substrings in a corpus, the substrings are grouped into a manageable number of equivalence classes. In this way, a prohibitive computation over substrings is reduced to a manageable computation over classes. This paper presents both the algorithms and the code that were used to compute term frequency (tf) and document frequency (df) for all n-grams in two large corpora, an English corpus of 50 million words of Wall Street Journal and a Japanese corpus of 216 million characters of Mainichi Shimbun. The second half of the paper uses these frequencies to find interesting substrings. Lexicographers have been interested in n-grams with high mutual information (MI) where the joint term frequency is higher than what would be expected by chance, assuming that the parts of the n-gram combine independently. Residual inverse document frequency (RIDF) compares document frequency to another model of chance where terms with a particular term frequency are distributed randomly throughout the collection. MI tends to pick out phrases with noncompositional semantics (which often violate the independence assumption) whereas RIDF tends to highlight technical terminology, names, and good keywords for information retrieval (which tend to exhibit nonrandom distributions over documents). The combination of both MI and RIDF is better than either by itself in a Japanese word extraction task.