关于这几种特殊情况的文件对比算法

Question

文件是由若干个消息组成，消息如下列出：

0|--MAP < MAP DELIMITER REQUEST < 发送 < 86-65535-255 -> :
1|--Detailed: time:2017-02-10 15:28:40.430, type:MAP
1|--Detailed: source:86-65535-255, dst:
1|--Detailed: direction:发送
         MAP_DeliReqEvent
    DialogID: 0x0007
             InvokeID: 0x00

每一条消息由0|--开始到最后的一个换行符结束。现在需要对两个文件中的每条消息的每个字段（可以理解为每一行）进行对比，但是有如下几种情况：

1. 这个文件中的这个消息只能与另外一个文件中的这个消息进行对比，但是消息不一定有序，比如某一条消息在这个文件中是第五条消息，在另外一个文件中可能是第十第二十这样的位置，同时可能存在某些消息只在一个文件中存在。

2. 消息有重名（如上面消息中的MAP < MAP DELIMITER REQUEST < 发送）但是下面的消息体会有不同，（所以便不能采用匹配消息名的办法定位到另一个文件中需要对比的消息）。

3. 假设已经定位到需要对比的两条消息，这两条消息不一定行数一样。

60%左右是可以按照消息位置进行匹配对比的，针对位置匹配以外的情况，个人认为主要的问题就是如何把消息乱序和消息缺失（或增加）区分开，以及适配相同的消息进行对比，最后找出两条消息中不同的字段（包括新增或缺失的）

我用的是python，刚开始的思路是把文件中的每一条消息的消息名按先后顺序存入一个字典dict1（即{0:'MAP < MAP DELIMITER REQUEST < 发送',1:'------',,,,,,,,}）,把需要对比的消息的每一行存入另一个字典{0: ['MAP_DeliReqEvent','DialogID: 0x0007','InvokeID: 0x00']},消息名和消息就按照字典中的键值一一对应起来了，当然这只是发现上面几种情况之前的想法，后面发现完全不能用这种思路了。请问大家有没有什么好的思路，大家一起讨论下，谢谢。

Answer 1

可以用消息ID和消息体里需要和字典匹配的消息体项目，一同生成一个唯一ID。比如你上面这个，
可以先生成一个这样的列表（可能我对你数据结构理解的还不是很清楚，不过做示例而已你能看得懂就行了）

[
    'id:86-65535-255',
    'time:2017-02-10 15:28:40.430',
    'type:MAP',
    'source:86-65535-255',
    'dst:',
    'direction:发送'
]

然后对这个列表进行排序（一定要排序，这样才能保证生成的ID值是唯一），比如按照字符串排序。
然后，以一个分隔符将列表连成字符串（比如|字符），接着计算一个特征值（比如，算出前面生成的这个唯一串的MD5）。

这样，一个代表整个配对信息的ID就生成了，以这个ID作为字典dict1的键名。

同样，对于你消息字典里的所有数据也进行这样的操作，生成dict2。

然后通过键名的配对，就可以完成dict1和dict2的对应项配对。由于键名是从数据里需要匹配的信息获取来的“信息指纹”，所以可以用消息指纹来定位整个消息。