python - 合并两个可能不相等的具有少量结构的列表

Question

我正在努力解决一个非常困难的问题。我想计算两个列表之间的某种差异度量。一个是经过验证的正确数据，另一个是由程序生成的。我想测试这个程序的准确性，但为了实现这一点，我需要以某种方式合并这两个列表。

可以在下面找到示例数据。

预期输出:字典列表，每个条目指定是否有两个匹配条目。如果它们不匹配，则应该有一个错误类型，指明出了什么问题。

输出列表的长度必须是两个列表中最大的一个，并且这个列表中的每个条目应该是以下之一:

• {"匹配": True}
• {"matching": False, "error_type": "deleted"}
• {"matching": False, "error_type": "inserted"}
• {"matching": False, "error_type": "updated"}

我在 Python 3 中工作，所以如果有人能提供 Python 代码那就太棒了，但是一些准确描述这种算法的伪代码会很有帮助!如果您找到一种更简单的方式来表示输出数据，那也很好。

到目前为止我所拥有的并不多，我真的不知道如何开始这个，但这是我目前拥有的少量代码:

compare_data = [{} for i in range(max(len(correct_data), len(program_data)))]
for i in range(len(compare_data)):
    if len(program_data) <= i:
        compare_data[i]['matching'] = False
        compare_data[i]['error_type'] = 'deleted'
    elif len(correct_data) <= i:
        compare_data[i]['matching'] = False
        compare_data[i]['error_type'] = 'inserted'
    elif correct_data[i]['type'] != program_data[i]['type']:
        compare_data[i]['matching'] = False
        compare_data[i]['matching'] = 'updated'
    else:
        compare_data[i]['matching'] = True
    # I really don't have a clue what to do...

我最初是在寻找某种通用的“合并具有相似结构的两个不相等列表”的算法可以应用于此，但我找不到实现此目的的算法。

正确的数据:

[
    {"type": "a", "data": ["some", "random"]},
    {"type": "b", "data": ["data", "for", "people", "to"]},
    {"type": "b", "data": ["mess", "with", "on", "stack"]},
    {"type": "b", "data": ["over", "flow", "so", "they"]},
    {"type": "c", "data": ["can", "try", "and"]},
    {"type": "d", "data": ["help", "me"]}
]

程序会产生各种错误数据，这里有几个例子:

• 缺少条目:

  [
      {"type": "a", "data":["some", "random"]},
      {"type": "b", "data":["data", "for", "people", "to"]},
      {"type": "b", "data":["mess", "with", "on", "stack"]},
      {"type": "c", "data":["can", "try", "and"]},
      {"type": "d", "data":["help", "me"]}
  ]
  

  预期输出:

  [
      {"matching": True},
      {"matching": True},
      {"matching": True},
      {"matching": False, "error_type": "delete"},
      {"matching": True},
      {"matching": True},
  ]
  

• 交换数据:

  [
      {"type": "a", "data":["some", "random"]},
      {"type": "b", "data":["mess", "for", "people", "stack"]},
      {"type": "b", "data":["data", "with", "on", "to"]},
      {"type": "b", "data":["over", "flow", "so", "they"]},
      {"type": "c", "data":["can", "try", "and"]},
      {"type": "d", "data":["help", "me"]}
  ]
  

  预期输出:

  [
      {"matching": True},
      {"matching": False, "error_type": "updated"},
      {"matching": False, "error_type": "updated"},
      {"matching": True},
      {"matching": True},
      {"matching": True},
  ]
  

• 多个不同类型的缺失条目:

  [
      {"type": "b", "data":["data", "for", "people", "to"]},
      {"type": "b", "data":["mess", "with", "on", "stack"]},
      {"type": "c", "data":["can", "try", "and"]},
      {"type": "d", "data":["help", "me"]}
  ]
  

  预期输出:

  [
      {"matching": False, "error_type": "deleted"},
      {"matching": True},
      {"matching": True},
      {"matching": False, "error_type": "deleted"},
      {"matching": True},
      {"matching": True},
  ]
  

• 相同类型的多个缺失条目:

  [
      {"type": "a", "data":["some", "random"]},
      {"type": "b", "data":["mess", "with", "on", "stack"]},
      {"type": "c", "data":["can", "try", "and"]},
      {"type": "d", "data":["help", "me"]}
  ]
  

  预期输出:

  [
      {"matching": True},
      {"matching": False, "error_type": "deleted"},
      {"matching": True},
      {"matching": False, "error_type": "deleted"},
      {"matching": True},
      {"matching": True},
  ]
  

• 添加条目(当然也可以添加多个条目):

  [
      {"type": "a", "data":["some", "random"]},
      {"type": "b", "data":["data", "for", "people", "to"]},
      {"type": "b", "data":["oops", "with", "got", "mangled"]},
      {"type": "b", "data":["mess", "these", "on", "stack"]},
      {"type": "b", "data":["over", "flow", "so", "they"]},
      {"type": "c", "data":["can", "try", "and"]},
      {"type": "d", "data":["help", "me"]}
  ]
  

  预期输出:

  [
      {"matching": True},
      {"matching": True},
      {"matching": False, "error_type": "updated"},
      {"matching": False, "error_type": "inserted"},
      {"matching": True},
      {"matching": True},
      {"matching": True}
  ]
  

Answer 1

你看起来很矛盾。差异不是那么容易得到正确的。

Python 的 difflib 内置了一些 diff 算法。如果您对结果满意，那么您可以使用下面概述的这种东西:

from difflib import SequenceMatcher

correct = [
    {"type": "a", "data": ["some", "random"]},
    {"type": "b", "data": ["data", "for", "people", "to"]},
    {"type": "b", "data": ["mess", "with", "on", "stack"]},
    {"type": "b", "data": ["over", "flow", "so", "they"]},
    {"type": "c", "data": ["can", "try", "and"]},
    {"type": "d", "data": ["help", "me"]}
]

compares = [
    ('Missing Entry',
     [
        {"type": "a", "data":["some", "random"]},
        {"type": "b", "data":["data", "for", "people", "to"]},
        {"type": "b", "data":["mess", "with", "on", "stack"]},
        {"type": "c", "data":["can", "try", "and"]},
        {"type": "d", "data":["help", "me"]}
    ]),
    ('Swapped data',
     [
        {"type": "a", "data":["some", "random"]},
        {"type": "b", "data":["mess", "for", "people", "stack"]},
        {"type": "b", "data":["data", "with", "on", "to"]},
        {"type": "b", "data":["over", "flow", "so", "they"]},
        {"type": "c", "data":["can", "try", "and"]},
        {"type": "d", "data":["help", "me"]}
    ]),
    # ...
        ]

def data_as_textlines(data):
    'Turns a list of dataitems into a list of each items repr string'
    return [repr(item) for item in data]


correct_text = C = data_as_textlines(correct)
for (title, prog_data) in compares:
    print('\n' + title)
    print('=' * len(title))
    prog_text = P = data_as_textlines(prog_data)
    s = SequenceMatcher(None, correct_text, prog_text)
    for tag, i1, i2, j1, j2 in s.get_opcodes():
        print('{:7}   C[{}:{}] --> P[{}:{}] {!r:>8} --> {!r}'.format(
            tag, i1, i2, j1, j2, correct_text[i1:i2], prog_text[j1:j2]))

其输出为:

Missing Entry
=============
equal     C[0:3] --> P[0:3] ["{'type': 'a', 'data': ['some', 'random']}", "{'type': 'b', 'data': ['data', 'for', 'people', 'to']}", "{'type': 'b', 'data': ['mess', 'with', 'on', 'stack']}"] --> ["{'type': 'a', 'data': ['some', 'random']}", "{'type': 'b', 'data': ['data', 'for', 'people', 'to']}", "{'type': 'b', 'data': ['mess', 'with', 'on', 'stack']}"]
delete    C[3:4] --> P[3:3] ["{'type': 'b', 'data': ['over', 'flow', 'so', 'they']}"] --> []
equal     C[4:6] --> P[3:5] ["{'type': 'c', 'data': ['can', 'try', 'and']}", "{'type': 'd', 'data': ['help', 'me']}"] --> ["{'type': 'c', 'data': ['can', 'try', 'and']}", "{'type': 'd', 'data': ['help', 'me']}"]

Swapped data
============
equal     C[0:1] --> P[0:1] ["{'type': 'a', 'data': ['some', 'random']}"] --> ["{'type': 'a', 'data': ['some', 'random']}"]
replace   C[1:3] --> P[1:3] ["{'type': 'b', 'data': ['data', 'for', 'people', 'to']}", "{'type': 'b', 'data': ['mess', 'with', 'on', 'stack']}"] --> ["{'type': 'b', 'data': ['mess', 'for', 'people', 'stack']}", "{'type': 'b', 'data': ['data', 'with', 'on', 'to']}"]
equal     C[3:6] --> P[3:6] ["{'type': 'b', 'data': ['over', 'flow', 'so', 'they']}", "{'type': 'c', 'data': ['can', 'try', 'and']}", "{'type': 'd', 'data': ['help', 'me']}"] --> ["{'type': 'b', 'data': ['over', 'flow', 'so', 'they']}", "{'type': 'c', 'data': ['can', 'try', 'and']}", "{'type': 'd', 'data': ['help', 'me']}"]

查看 difflib.SequenceMatcher.get_opcodes 的文档您会在他们的示例中发现某些相似之处:-)