Fuzzy match

[barthanssens]

Maybe fuzzywuzzy can help https://github.com/seatgeek/fuzzywuzzy

[theodedeken]

I have an idea for a performant way to do fuzzy matching but might not have enough time to fully implement it, so leaving this here as a reminder.

Idea

Basically I would solve it as a tree search algorithm using branch and bound to reduce the amount of comparison that need to be made.

We create our tree using dictionaries and use a different table column to index each of the levels. We start with the column with the least unique entries so the amount of entries on each level are limited.

We match each column of the address separately, the overall match of the address is the average of all the parts.

We go over each entry of a level starting with the entry with the highest ratio (of that part of the address), skipping the entries where the ratio will not be better than the current maximum.

The heuristic for the branch and bound

Fuzzywuzzy returns a ratio of how well a string matches as a number between 0 and 1 (1 being exact). So if we assume that the parts that we haven't compared yet are exact we can create a bound that will never be lower than the actual match ratio. If this heuristic is lower than the current best result we can stop traversing the current branch of the tree.