将属于一起的文档部分分组的算法
Algorithm to group parts of documents that belong together
我有同一份文件的 N 份翻译，分为多个部分（我们称它们为节）。有些译本省略了一些经文。没有翻译包含所有的经文。
我想 'align' 基于内容的翻译（即在数据库中创建记录或在电子表格中创建行），方法是创建组。每组应包含 M 节经文，其中 M 是该节经文出现的翻译次数，M < N。每节经文不得属于多个组。
到目前为止我所拥有的（使用可用于 Python 的各种 API）：
- 构建所有翻译中所有经文的一维列表（跟踪哪些经文来自哪些翻译）
- 每节经文：
- 使用 Google Translate
将这节经文翻译成英语
- 获取该经文相对于所有其他经文的 tf-idf 相似度
- 在所有其他翻译中找到最相似的经文
实际上，我最终得到了一个带有方向边的图。每条边都有一个可能性（百分比），它显示它指向的经文与它指向的经文的相似性。
示例：
- N = 3 个翻译
- 每个翻译有 2 节经文
- 正确的分组（就像人类将它们分组一样）是 (A,B,C)，(D,E,F)
- 我的算法给出：
正确的分组对人眼来说是显而易见的。
如何扩展这个算法来实现我需要的分组？结果将由人工检查，因此不需要完美，但必须自动化。
一些定义使解释更容易：
P(x,y) - 从节点 a 到 b 的概率。 （例如上面 - P(a,b)=77 和 P(b,a)=85）。
CP(x,y) - 组合概率。可以是 P(x,y) * P(y,x) 或 P(x,y) + P(y,x).
我建议的算法如下：
找到一对x, y最高的CP(x, y)，然后将它们视为一个节点（a.k.a。x_y）。重新计算图形，以便考虑到任何两个节点的每条边。使用图形的矩阵表示可以非常有效地完成此操作。
重复此步骤，直到您有 M 个组。
如果诗句按照您在评论中所写的顺序排序，那么这很容易表述为 edit distance 问题。
首先假设你只有两种语言。您可以按如下方式重新表述您的问题：您需要通过以下操作将一种翻译 (A) 转换为另一种 (B)：您可以删除一节经文（这意味着该节经文出现在A，但 B 中没有），您可以插入一节经文（这意味着它不存在于 A，但存在于 B 中），或者您可以替换一个与另一节经文（意思是你匹配这两节经文）。您可以为这些操作中的每一个分配成本；替换的成本将取决于您已经计算出的相似度，并且您需要以某种方式定义插入或删除的成本（您可能需要对此进行试验）。在此之后，你 运行 维基百科中提到的标准算法，你在二次时间得到你的匹配。
如果你有两种以上的语言，你可以使用类似的精确算法，但它会 运行 慢（O(N^k) 和 N 开始最大数量的经文和k 从语言数量开始），或者您可以使用一些近似算法，例如先匹配两种语言，然后添加第三种语言等。
我有同一份文件的 N 份翻译，分为多个部分（我们称它们为节）。有些译本省略了一些经文。没有翻译包含所有的经文。
我想 'align' 基于内容的翻译（即在数据库中创建记录或在电子表格中创建行），方法是创建组。每组应包含 M 节经文，其中 M 是该节经文出现的翻译次数，M < N。每节经文不得属于多个组。
到目前为止我所拥有的（使用可用于 Python 的各种 API）：
- 构建所有翻译中所有经文的一维列表（跟踪哪些经文来自哪些翻译）
- 每节经文：
- 使用 Google Translate 将这节经文翻译成英语
- 获取该经文相对于所有其他经文的 tf-idf 相似度
- 在所有其他翻译中找到最相似的经文
实际上，我最终得到了一个带有方向边的图。每条边都有一个可能性（百分比），它显示它指向的经文与它指向的经文的相似性。
示例：
- N = 3 个翻译
- 每个翻译有 2 节经文
- 正确的分组（就像人类将它们分组一样）是 (A,B,C)，(D,E,F)
- 我的算法给出：
如何扩展这个算法来实现我需要的分组？结果将由人工检查，因此不需要完美，但必须自动化。
一些定义使解释更容易：
P(x,y) - 从节点 a 到 b 的概率。 （例如上面 - P(a,b)=77 和 P(b,a)=85）。
CP(x,y) - 组合概率。可以是 P(x,y) * P(y,x) 或 P(x,y) + P(y,x).
我建议的算法如下：
找到一对x, y最高的CP(x, y)，然后将它们视为一个节点（a.k.a。x_y）。重新计算图形，以便考虑到任何两个节点的每条边。使用图形的矩阵表示可以非常有效地完成此操作。
重复此步骤，直到您有 M 个组。
如果诗句按照您在评论中所写的顺序排序，那么这很容易表述为 edit distance 问题。
首先假设你只有两种语言。您可以按如下方式重新表述您的问题：您需要通过以下操作将一种翻译 (A) 转换为另一种 (B)：您可以删除一节经文（这意味着该节经文出现在A，但 B 中没有），您可以插入一节经文（这意味着它不存在于 A，但存在于 B 中），或者您可以替换一个与另一节经文（意思是你匹配这两节经文）。您可以为这些操作中的每一个分配成本；替换的成本将取决于您已经计算出的相似度，并且您需要以某种方式定义插入或删除的成本（您可能需要对此进行试验）。在此之后，你 运行 维基百科中提到的标准算法，你在二次时间得到你的匹配。
如果你有两种以上的语言，你可以使用类似的精确算法，但它会 运行 慢（O(N^k) 和 N 开始最大数量的经文和k 从语言数量开始），或者您可以使用一些近似算法，例如先匹配两种语言，然后添加第三种语言等。