Using sequence matcher in Python to find the longest common string

Question

I was trying to use difflib.SequenceMatcher in Python to return the largest common string

string1="""ERROR agave_util.py:64 Timed out waiting for HA alert generated CRITICAL ha_test_util.py:44 HA alert generated, Stack:File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 909, in <module>    main(FLAGS, sync_state)  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 878, in main    worker.run(sync_state)  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 326, in run    if not self.__test_phase_wrapper(test_method):  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 502, in __test_phase_wrapper    func()  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 87, in test_stargate_master_power_off    self._host_power_off_test_cycle(host_of_stargate_master)  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 27, in _host_power_off_test_cycle    self.ha_util.power_off_and_check_ha(host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 469, in power_off_and_check_ha    self.wait_for_ha_alert(cutoff_usecs=latest_alert_start, **kwargs)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 418, in wait_for_ha_alert    interval=interval,  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 44, in wait_for_true    CHECK(result, message) ERROR nutanix_test_runner_worker.py:595 Test failed: 1exc_type: <type 'exceptions.SystemExit'>exc_value: 1stack:   File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 502, in __test_phase_wrapper    func()  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 87, in test_stargate_master_power_off    self._host_power_off_test_cycle(host_of_stargate_master)  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 27, in _host_power_off_test_cycle    self.ha_util.power_off_and_check_ha(host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 469, in power_off_and_check_ha    self.wait_for_ha_alert(cutoff_usecs=latest_alert_start, **kwargs)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 418, in wait_for_ha_alert    interval=interval,  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 44, in wait_for_true    CHECK(result, message)  File "/main/.python/util/base/log.py", line 204, in CHECK    FATAL(log_msg, **kwargs)  File "/main/.python/util/base/log.py", line 185, in FATAL    sys.exit(1) ERROR nutanix_test.py:696 Failed to get gflags from 10.5.132.157. ERROR nutanix_test.py:696 Failed to get gflags from 10.5.132.157. ERROR nutanix_test.py:1699 Failed to save cluster configuration"""

string2="""ERROR agave_util.py:64 Timed out waiting for VMs [u'vm_353ca5', u'vm_e02d7f'] power on CRITICAL ha_test_util.py:44 VMs [u'vm_353ca5', u'vm_e02d7f'] power on, Stack:File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 909, in <module>    main(FLAGS, sync_state)  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 878, in main    worker.run(sync_state)  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 326, in run    if not self.__test_phase_wrapper(test_method):  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 502, in __test_phase_wrapper    func()  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 67, in test_zoo_keeper_leader_power_off    self._host_power_off_test_cycle(leader_host)  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 27, in _host_power_off_test_cycle    self.ha_util.power_off_and_check_ha(host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 468, in power_off_and_check_ha    self.verify_vms_not_on_host(host_vms, host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 617, in verify_vms_not_on_host    self.wait_for_vms_power_on(vm_names, per_vm_timeout)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 599, in wait_for_vms_power_on    interval=15)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 44, in wait_for_true    CHECK(result, message) ERROR nutanix_test_runner_worker.py:595 Test failed: 1exc_type: <type 'exceptions.SystemExit'>exc_value: 1stack:   File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 502, in __test_phase_wrapper    func()  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 67, in test_zoo_keeper_leader_power_off    self._host_power_off_test_cycle(leader_host)  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 27, in _host_power_off_test_cycle    self.ha_util.power_off_and_check_ha(host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 468, in power_off_and_check_ha    self.verify_vms_not_on_host(host_vms, host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 617, in verify_vms_not_on_host    self.wait_for_vms_power_on(vm_names, per_vm_timeout)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 599, in wait_for_vms_power_on    interval=15)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 44, in wait_for_true    CHECK(result, message)  File "/main/.python/util/base/log.py", line 204, in CHECK    FATAL(log_msg, **kwargs)  File "/main/.python/util/base/log.py", line 185, in FATAL    sys.exit(1) ERROR nutanix_test.py:696 Failed to get gflags from 10.5.132.156. ERROR nutanix_test.py:696 Failed to get gflags from 10.5.132.156. ERROR nutanix_test.py:1699 Failed to save cluster configuration"""

match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))
print match
print(string1[match.a: match.a + match.size])

string1="""ERROR agave_util.py:64 Timed out waiting for HA alert generated CRITICAL ha_test_util.py:44,"""
string2="""ERROR agave_util.py:64 Timed out waiting for VMs [u'vm_353ca5', u'vm_e02d7f'] power on CRITICAL ha_test_util.py:44"""
match = SequenceMatcher(None, string1, string2).find_longest_match(0,    len(string1), 0, len(string2))
print(string1[match.a: match.a + match.size])

So basically during comparison of string1 and string2 [first two lines] returns CRITICAL ha_test_util.py:44, while when I cut some lines from string1 and string2 [lines 6 and 7], it returned ERROR agave_util.py:64 Timed out waiting for

Basically my question is why sequence matcher didn't return the proper match during my first case?

Answer 1

You are experiencing (in your case negative) effects of SequenceMatcher's automatic junk heuristic. From the docs:

Automatic junk heuristic: SequenceMatcher supports a heuristic that automatically treats certain sequence items as junk. The heuristic counts how many times each individual item appears in the sequence. If an item’s duplicates (after the first one) account for more than 1% of the sequence and the sequence is at least 200 items long, this item is marked as “popular” and is treated as junk for the purpose of sequence matching. This heuristic can be turned off by setting the autojunk argument to False when creating the SequenceMatcher.

In SequenceMatcher constructor, autojunk defaults to True. If you try with autojunk=False, you'll get the expected longest match:

from difflib import SequenceMatcher

string1 = """ERROR agave_util.py:64 Timed out waiting for HA alert generated CRITICAL ha_test_util.py:44 HA alert generated, Stack:File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 909, in <module>    main(FLAGS, sync_state)  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 878, in main    worker.run(sync_state)  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 326, in run    if not self.__test_phase_wrapper(test_method):  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 502, in __test_phase_wrapper    func()  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 87, in test_stargate_master_power_off    self._host_power_off_test_cycle(host_of_stargate_master)  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 27, in _host_power_off_test_cycle    self.ha_util.power_off_and_check_ha(host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 469, in power_off_and_check_ha    self.wait_for_ha_alert(cutoff_usecs=latest_alert_start, **kwargs)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 418, in wait_for_ha_alert    interval=interval,  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 44, in wait_for_true    CHECK(result, message) ERROR nutanix_test_runner_worker.py:595 Test failed: 1exc_type: <type 'exceptions.SystemExit'>exc_value: 1stack:   File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 502, in __test_phase_wrapper    func()  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 87, in test_stargate_master_power_off    self._host_power_off_test_cycle(host_of_stargate_master)  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 27, in _host_power_off_test_cycle    self.ha_util.power_off_and_check_ha(host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 469, in power_off_and_check_ha    self.wait_for_ha_alert(cutoff_usecs=latest_alert_start, **kwargs)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 418, in wait_for_ha_alert    interval=interval,  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 44, in wait_for_true    CHECK(result, message)  File "/main/.python/util/base/log.py", line 204, in CHECK    FATAL(log_msg, **kwargs)  File "/main/.python/util/base/log.py", line 185, in FATAL    sys.exit(1) ERROR nutanix_test.py:696 Failed to get gflags from 10.5.132.157. ERROR nutanix_test.py:696 Failed to get gflags from 10.5.132.157. ERROR nutanix_test.py:1699 Failed to save cluster configuration"""
string2 = """ERROR agave_util.py:64 Timed out waiting for VMs [u'vm_353ca5', u'vm_e02d7f'] power on CRITICAL ha_test_util.py:44 VMs [u'vm_353ca5', u'vm_e02d7f'] power on, Stack:File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 909, in <module>    main(FLAGS, sync_state)  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 878, in main    worker.run(sync_state)  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 326, in run    if not self.__test_phase_wrapper(test_method):  File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 502, in __test_phase_wrapper    func()  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 67, in test_zoo_keeper_leader_power_off    self._host_power_off_test_cycle(leader_host)  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 27, in _host_power_off_test_cycle    self.ha_util.power_off_and_check_ha(host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 468, in power_off_and_check_ha    self.verify_vms_not_on_host(host_vms, host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 617, in verify_vms_not_on_host    self.wait_for_vms_power_on(vm_names, per_vm_timeout)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 599, in wait_for_vms_power_on    interval=15)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 44, in wait_for_true    CHECK(result, message) ERROR nutanix_test_runner_worker.py:595 Test failed: 1exc_type: <type 'exceptions.SystemExit'>exc_value: 1stack:   File "/main/qa/py/qa/agave/nutanix_test_runner_worker.py", line 502, in __test_phase_wrapper    func()  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 67, in test_zoo_keeper_leader_power_off    self._host_power_off_test_cycle(leader_host)  File "/main/qa/test/agave/acropolis_tests/ha/best_effort_power_off_test.py", line 27, in _host_power_off_test_cycle    self.ha_util.power_off_and_check_ha(host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 468, in power_off_and_check_ha    self.verify_vms_not_on_host(host_vms, host)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 617, in verify_vms_not_on_host    self.wait_for_vms_power_on(vm_names, per_vm_timeout)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 599, in wait_for_vms_power_on    interval=15)  File "/main/.python/qa/util/agave_tools/ha_test_util.py", line 44, in wait_for_true    CHECK(result, message)  File "/main/.python/util/base/log.py", line 204, in CHECK    FATAL(log_msg, **kwargs)  File "/main/.python/util/base/log.py", line 185, in FATAL    sys.exit(1) ERROR nutanix_test.py:696 Failed to get gflags from 10.5.132.156. ERROR nutanix_test.py:696 Failed to get gflags from 10.5.132.156. ERROR nutanix_test.py:1699 Failed to save cluster configuration"""

match = SequenceMatcher(None, string1, string2, autojunk=False).find_longest_match(0, len(string1), 0, len(string2))
print(match)

Output:

Match(a=110, b=156, size=534)

To be sure, we can check all matching blocks and find the longest:

>>> max(SequenceMatcher(None, string1, string2, autojunk=False).get_matching_blocks(),
...     key=lambda m: m.size)
Match(a=110, b=156, size=534)

---

To illustrate the effects of autojunking on a simpler example, let's have a look what happens here:

>>> a = "aa:bb:cc" + ":"*200
>>> b = "aa:bb" + ":"*200
>>> SequenceMatcher(None, a, b).find_longest_match(0, len(a), 0, len(b))
Match(a=0, b=0, size=6)     # : is classified as junk
>>> SequenceMatcher(None, a, b, autojunk=False).find_longest_match(0, len(a), 0, len(b))
Match(a=8, b=5, size=200)   # : is NOT classified as junk

In the first case (with default autojunk=True) the : is considered a junk character (it represents more than 1% of the sequence that's at least 200 items long), and as the result, the longest match that "looks right to people" is only 6 characters (the initial six).

In the second case (with explicit autojunk=False), the junk heuristics is off, and so the longest match is the last 200 characters.

If you repeat the same test for shorter sequences (shorter than 200 characters), you can see the autojunk makes no difference, since the junk heuristics is turned off (see in source).