Better fuzzy search for OCRed documents

[0x-Apollyon]

Hey so I have been using ugrep's fuzzy search feature for some of my university projects which involve OCR scanning huge corpus of documents. One problem which I run into often is that finetuning the edit distance parameter to match common OCR errors, is a bit of chore.

My current pipeline is somewhat similar to what is describe in #304, followed by manual scanning as I have to keep the edit distance a bit wide to get all possible OCR errors

I propose a sort of OCR aware fuzzy search, something like:

Normal edit distance:

rn → m cost 2
I → l cost 1
O → 0 cost 1

OCR aware:

rn → m cost ~0.5
I → l cost ~0.2
O → 0 cost ~0.2

We can let the user describe these configurations, and if possible, have some preset ones for common OCR technologies like Tesseract

[genivia-inc]

Thank you for your suggestion.

[genivia-inc]

I wonder if it would help to change the search pattern to include often misread characters? If these mismatches should have a low error rate, then you could change a search pattern such as loom into [Il][o0][o0](rn|m). But perhaps that matches too much? Note that the first character in the search pattern must match, so [Il] (capital I and lower case l) is desired anyway.

[0x-Apollyon]

Yeah the matching too much is one of the issues I faced as such matching gets really broad really fast and as I mentioned earlier, maintaining a regex for many such characters is really cumbersome, especially when we take into account letters which have multiple homoglyphs (lower L, the number 1, upper case i)

[0x-Apollyon]

If other tasks are higher up on the priority list, let me know how (and if) youd like such a feature to be implemented and Id be happy to help, as this functionality would personally help me a lot and also can be a way I give back to open source projects which I use :)

[genivia-inc]

Yeah the matching too much is one of the issues I faced as such matching gets really broad really fast and as I mentioned earlier, maintaining a regex for many such characters is really cumbersome, especially when we take into account letters which have multiple homoglyphs (lower L, the number 1, upper case i)

I agree, using a regex for OCR errors is not great and something that fuzzy matching is better at.

I need to figure this out first before I can give a definite answer to include the enhancement request as a new feature. Character-by-character replacements are relatively easy to compute with a fractional edit distance. Multi-character replacement fractional edit distances are more challenging, because these involve deletions and insertions that always count as 1 edit distance. So 'rn' -> 'm' will always count as >1 edit. The edit distance is computed on the fly while matching, using a limited form of backtracking to find more edit-based matches until the edit distance does not exceed the given max. When this edit distance always exceeds the max then we move on to the next match. This is much faster than computing the minimum edit distance of the pattern at every possible position in the input. That would be OK for strings (using the Dynamic Programming method), but not so for a regex that can match in many different ways the same input which means that all possible insertions, replacements, and deletions can quickly pile up.

[0x-Apollyon]

Ok so correct me if im wrong anywhere as my prior knowledge of algorithms to calculate levenshtein distance and regex is limited to what is taught in an undergrad algorithms class. What I understand is that at every step of the way, if there is a mismatch, ugrep's fuzzy logic creates branches based on what type of edit it is when it encounters a mismatch between the regex and the text its going through and kills off the branches when they exceed the limit set by the user

For multi character edits, can we add a sort of macro transition branch where it matches a known OCR error my looking ahead and consuming multiple characters from the text or the regex (bidirectional) at once and some memoization to handle paths converging on the same state with different costs. The memoization thing can be a bit tricky to implement and if it doesnt already exist in the core engine