I needed a way to match banking statements -- exported from my bank and inserted into hledger -- into correct accounts. The idea was to find common strings between a few statements of the same account and test against ones that go into a different account. Spoiler: I was overthinking the problem. A simple "Aldi" in the cascade of IFs is enough. I am proofreading this automatic matches either way, so some errors are ok and can be fixed in the matching code later.
Still I implemented some longest common sequence algorithm and a small webservice to find them and test against a negative list. The full code is in https://github.com/mfa/longest-common-sequence and is currently hosted at https://lcs.madflex.de/. I will probably undeploy this in a few weeks.
Things I learned:
There is a
SequenceMatcher readily available in difflib in Python.
This matches two strings and gives the longest matching blocks by calling get_matching_blocks.
combinations from itertools (also Python core) to find the matches for every combination of string pairs.
The whole idea is to get a list of common strings between all string pair combinations, then test the match_strings against the positive and then against the negative examples given.
The positive matches are reduced by checking every matched_string with
all(map(lambda x: match_string in x, positives_examples)) and the negatives by an
The full code is in algorithm.py.
The website looks like this: