algorithm - 实时数据匹配算法

Question

我有一组(整数)输入值和一组期望值，例如

000033335502200008777
000033335552200007777

在这个示例中，我有零输入，应该忽略它和非零输入组:

3333
555
22
7777

输入数据可能有

1. 不同长度的组(550 和 555)
2. 组类 (0055500 0555000)
3. 错误(但接近)的值(8777 和 7777)

对于每个这样的组，我希望有这样的匹配率:

3333 (100%)
555  (66.67%)
22 (100%)
7777 (75%)

重要的一点是我在每组处理完成后立即需要这个比率:

first ratio after 8 values
second ratio after 11 values
third ratio after 13 values
fourth ratio after 21 values

我应该选择什么算法/方法？

提前致谢!

Answer 1

实际上，有一些来自计算生物学和遗传学的算法可能适用于快速数字匹配，也适用于序列模式挖掘领域。

查看 S. S. Sheik、Sumit K. Aggarwal Anindya Poddar N. Balakrishnan‡ 和 K. Sekar 的“A FAST 模式匹配算法”

此外，您似乎可以从研究字符串组件之间匹配的算法中获益。

一些众所周知的是 Smith-Waterman , 和 Needleman-Wunsch . 对于直接字符串匹配，我建议查看 Jaro-Winkler和 Monge-Elkan。