Large Scale Parallel Document Mining for Machine Translation
以前的对齐文档挖掘依赖于metadata，比如发布日期。但web内容是非结构化的。
系统描述
- 将所有文档翻译为英文
- 提取match n-gram（构建候选集合）和score n-gram（计算document得分）
这个阶段生成两个索引，forward index列出所有提取的score n-gram，按文档索引。
倒排索引，match n-gram匹配的所有文档，match n-gram作为索引。
倒排索引还用于累计出现score n-gram 文档的频率等 - 为倒排索引中每个mache n-gram生成文档对。只保留源自不同语言的对，删除单一n-gram或单一语言文档。
- 丢弃匹配频率超过一定阈值的match ngram。由于match ngram的长尾分布，仅会导致一小部分的n-gram被过滤掉。（这个过滤步骤会导致系统运行的整体时间和输出数据呈线性关系）
- 根据score n-gram文档频率更新forward index（pairwise scoring）
- 计算所有候选文档的pairwise scores，分数低于一定阈值的将会被丢掉。为每种语言生成一个n-best列表
- 从n-best列表中丢弃非对称文档。
pairwise scoring
对于文档\(d_1\)和\(d_2\)
\(F_{d_{1}}={f_1,f_2,...,f_n}\)score ngram的集合
\(idf(f)=log\frac{D}{df(f)}\) D输出的文档个数，df(f)是包含ngram f的文档个数。
将\(F_{d_{1}},F_{d_{2}}\)视为特征向量。
通过余弦相似度来计算两个文档的相似评分。
作者在初步实验中，结合词频得到基本的tf/idf，以及使用其他结合词频的信息检索排序函数，如bm25，与上述更简单的评分函数相比，性能有所下降。
除此之外，作者新增了一个score n-gram相对位置距离的过滤条件，保证，score ngram的顺序基本一致。在统计score ngram信息时，也会抽取他的相对位置存储在forward index中。
计算复杂度
c：倒排索引中match ngram出现的最大次数。
m：表示单个文档中提取match ngram小于c的平均文档数
D：输入的文档数
系统生成的候选文档数最大为：\(xD*c*m\),针对候选文档，我们需要计算pair score（score n-gram点积），假设score ngram格式为s。最终的复杂度为\(O(D*m*c*s)\)
句子级别对齐
是用动态规划句子对齐算法，以句子长度和多语言概率字典，对每个句子进一步过滤。粗略的对齐source target句子单词。这种粗略的对齐只用于过滤不平行的句子。
p(s,t),p(s),p(t)都是单词对齐语料库中的经验分布（统计），结果除以近似期望值
丢弃了实际得分与期望得分之比小于1/3的句子
参数选择
