belambert / edit-distance Goto Github PK

I get an extreme memory consumption when trying to align very long sequences with Python 3.6 (strings of about 10k characters). Calling SequenceMatcher.get_opcodes() never terminates, allocating more and more (up to 28 GB resident) until interrupted. This happens even with identical a and b, as long as the sequence is long enough.

Minimal example:

from edit_distance.code import SequenceMatcher
a = u"x" * 10000 # dummy text
b = u"x" * 10000 # same
matcher = SequenceMatcher(a, b)
matcher.get_opcodes()

Thanks for the code,
Any idea on how to implement list of list functionality?

Instead of:
['a','b','c']
['a','b','c','d']

This
['a','b',['c']]
['a','b',['c','d','e']]

And the algorithm is allowed to add 'd' and 'e' inside the third element.

Instead of outputting an integer edit distance value, is it possible to decompose the edit distance so as to see how many insertions, deletions and substitutions are needed?

The insert index returned by get_opcodes() appears to be off by -1.

Example:
from difflib import SequenceMatcher
sm = SequenceMatcher(a='abc', b='abdc')
print(sm.get_opcodes())

from edit_distance import SequenceMatcher
sm = SequenceMatcher(a='abc', b='abdc')
print(sm.get_opcodes())

output:
[('equal', 0, 2, 0, 2), ('insert', 2, 2, 2, 3), ('equal', 2, 3, 3, 4)]
[['equal', 0, 1, 0, 1], ['equal', 1, 2, 1, 2], ['insert', 1, 1, 2, 3], ['equal', 2, 3, 3, 4]]

the "insert" opcode index should be 2 (not 1).

Hi there,

I have an AssertionError thrown by this line of code. What does it mean? Shall I be worried? Is there any way to inspect what is happening in depth?

The two arrays of symbols I am comparing are the following:

• ['that', 'continuous', 'sanction', ':=', '(', 'flee', 'U', 'complain', ')', 'E', 'attendance', 'eye', '^', 'flowery', 'revelation', '^', 'ridiculous', 'destination', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>']
• ['continuous', ':=', '(', 'sanction', '^', 'flee', '^', 'attendance', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>', '<EOS>']

Thanks in advance,
Giulio

P.S. I know my data look weird, please don't ask what they are about :-)