algorithm - 推导字符串转换规则

Question

我有一组字符串对，例如:

阿爸阿爸，哈哈 - 啊哈，咩咩，前 - 特别是，xa - za

该对中的第二个(右)字符串与第一个(左)字符串有些相似。

也就是说，第一个字符串中的一个字符可以什么都没有表示，它本身也可以是一小组字符中的一个字符。

虽然有一些模式，但对于这种字符到字符的映射没有简单的规则。

给定数千个这样的字符串对，我如何推导出转换规则，如果我将它们应用于左侧字符串，我将得到正确的字符串？

该解决方案可以是近似的，例如对 80-95% 的字符串都能正常工作。

您会推荐使用某种遗传算法吗？如果是，怎么办？

Answer 1

如果您可以对齐字符，或者更确切地说是字符组，您可以计算出表示 aa => a、bb => z 等的表格。如果你有这样的表格，你可以使用 http://en.wikipedia.org/wiki/Dynamic_time_warping 来对齐字符。 .因此，一种方法是猜测对齐方式(例如，一对一，作为起点，或者只是对齐每个序列的第一个和最后一个字符)，从中计算出一个翻译表，使用 DTW 获得新的对齐方式，工作出一个修改后的翻译表，并以这种方式迭代。或许您可以用足够的数学来总结这一点，以表明存在某种最优性度量或此类传递增加的概率，攀升至局部最大值。

可能有某种方法可以通过对同时生成两个序列的隐马尔可夫模型建模然后从该模型中导出规则来实现这一点，但我不会选择这种方法，除非我已经熟悉 HMM 并且有软件可以用作我很乐意修改的起点。