Writing a fuzzy receipt parser in Python
tech.trivago.com
tech.trivago.com
QR codes can hold a little over 1,200 characters, which should be more than enough for most receipts.
https://en.wikipedia.org/wiki/QR_code#Storage
Edit: related link: https://www.quora.com/Can-and-how-cash-register-receipts-be-...
Stores that are mandated to issue receipts are giving away trade secrets. If the format was standardized and easily readable then it'd be much easier for competitors to analyze their data.
But I think it's much more likely that we'll sooner see itemized electronic receipt data from the smartphone-based payment brokers (Apple Pay, Android Pay, etc) -- assuming it doesn't already do that.
You could do some pretty amazing things in QR codes by base64 encoding compressed textual data.
> Market name > Examplestreet 12 > 19393 Examplecity
while others use:
> Market name > 19393 Examplecity > Examplestreet 12
We're not even talking about the invoice/receipt layout. It's different all the time.
But depending on the length of the receipt, the total is always at a different place. Another problem was that the detection rate of tesseract for whole words was pretty low to begin with. So searching for exact words like total or sum didn't work. So even though you could give the parser a rough area to look for the total, you would still need to do some fuzzy matching on "total" and "sum" to get it right.
In the end it's most important that it works for as many cases as possible. Getting to 60% was trivial but after that it got interesting. ;-)
Question: have you thought about any better methods for getting the receipts scanned? A big hurdle for me was the time it took to scan everything. I know there are scanners designed for such a thing, and you seem to have used one, but were you satisfied with it?
And thanks for the get_close_matches() hint! I'll try and remember that if I ever start hacking again on this.
When it comes to rotation, you can try http://www.fmwconcepts.com/imagemagick/textcleaner/. It will rotate your scan if it's not perfectly aligned.
One trick I've found is to use it in both directions and then only using results that agree both ways.
Something like this (very terse version):
closest_or_none = lambda l, options: (difflib.get_close_matches(l, options, n=1) or [None])[0]
dir1 = [(l, closest_or_none(l, list2)) for l in list1]
dir2 = [(closest_or_none(l, list1), l) for l in list2]
one_to_one = set(dir1).intersection(set(dir2))
You ended up with 127 usable scans, and then used all 127 scans as your test data set while developing. You run the risk, here, of 'overfitting' your data set. That is to say, you figure out a set of parameters and techniques that gets a good match rate (98%) on your test data set, but fails when you try it on new data.
There's a useful technique in machine learning and statistics, called Cross Validation. There's different specific techniques, but basically, you should split up your dataset into training (80%ish) and validation (20%ish) sets, randomly sampled. You develop with just the training set, and when you have a good match rate, you test if it also is good on your validation set. This helps you detect if your technique actually generalizes to new input well, or if it just happens to match what you trained on.
I also wanted fuzzy string matching, but I ended up writing my own clusterer in C to get the speed I wanted, and then wrapped it up as a python module. Must admit I hadn't considered difflib. The c code now lives in ccan[2]. I've got a patch to add the string vector cosine measurement as a filter which gives quite a big performance boost. As a rough indicator, on my laptop it clusters 3500 transaction descriptions in about 600ms.
Anyone know any resources or an idea for direction to get started on this?
Look here: http://stackoverflow.com/questions/4196453/simple-and-fast-m... http://stackoverflow.com/questions/11541154/checking-images-...
Disclaimer: I work for the company.
Are you perhaps going to offer some insight about the author's attempts, and what alternative experiences you've had implementing your functionality, or what solutions/algorithm's you've used?