Algorithms or Patterns for reading text

Question

My company has a client that tracks prices for products from different companies at different locations. This information goes into a database.

These companies email the prices to our client each day, and of course the emails are all formatted differently. It is impossible to have any of the companies change their format - they will not do it.

Some look sort of like this:

    This is example text that could be many lines long...

    Location 1
    Product 1     Product 2     Product 3
    $20.99        $21.99        $33.79

    Location 2
    Product 1     Product 2     Product 3
    $24.99        $22.88        $35.59

Others look sort of like this:

    PRODUCT       PRICE    + / -
    ------------  -------- -------
    Location 1
    1             2007.30 +048.20
    2             2022.50 +048.20

    Maybe some multiline text here about a holiday or something...

    Location 2
    1             2017.30 +048.20
    2             2032.50 +048.20

Currently we have individual parsers written for each company's email format. But these formats change slightly pretty frequently. We can't count on the prices being on the same row or column each time.

It's trivial for us to look at the emails and determine which price goes with which product at which location. But not so much for our code. So I'm trying to find a more flexible solution and would like your suggestions about what approaches to take. I'm open to anything from regex to neural networks - I'll learn what I need to to make this work, I just don't know what I need to learn. Is this a lex/parsing problem? More similar to OCR?

The code doesn't have to figure out the formats all on its own. The emails fall into a few main 'styles' like the ones above. We really need the code to just be flexible enough that a new product line or whitespace or something doesn't make the file unparsable.

Thanks for any suggestions about where to start.

Answer 1

You have given two pattern samples for text files.
I think these can be handled with scripting.
Something like: AWK, sed, grep with bash scripting.

---

One pattern in the first sample,

1. Section starts with keyword Location [Number]
2. second line of section has columns describing product names
3. third line of section has columns with prices for the products

There can be variable number of products per section.
There can be variable number of sections per file.
Products and prices are always on their designated lines of a section.
Whitespace separation identifies the (product,price) column-association.
Number of products in a section matches the number of prices in that section.

---

The collected data would probably be assimilated in a database.

Answer 2

The one thing I know I would use here is regular expressions. Three or four expressions could drive the parse logic for each e-mail format.

Trying to write the parse engine more generally than that would, I think, be skirting the edge of overprogramming it.

Answer 3

I think this problem would be suitable for proper parser generator. Regular expressions are too difficult to test and debug if they go wrong. However, I would go for a parser generator that is simple to use as if it was part of a language.

For these type of tasks I would go with pyparsing as its got the power of a full lr parser but without a difficult grammer to define and very good helper functions. The code is easy to read too.

from pyparsing import *

aaa ="""    This is example text that could be many lines long...
             another line

    Location 1
    Product 1     Product 2     Product 3
    $20.99        $21.99        $33.79

    stuff in here you want to ignore

    Location 2
    Product 1     Product 2     Product 3
    $24.99        $22.88        $35.59 """

result = SkipTo("Location").suppress() \  
# in place of "location" could be any type of match like a re.
         + OneOrMore(Word(alphas) + Word(nums)) \
         + OneOrMore(Word(nums+"$.")) \

all_results = OneOrMore(Group(result))

parsed = all_results.parseString(aaa)

for block in parsed:
    print block

This returns a list of lists.

['Location', '1', 'Product', '1', 'Product', '2', 'Product', '3', '$20.99', '$21.99', '$33.79']
['Location', '2', 'Product', '1', 'Product', '2', 'Product', '3', '$24.99', '$22.88', '$35.59']

You can group things as you want but for simplicity I have just returned lists. Whitespace is ignored by default which makes things a lot simpler.

I do not know if there are equivalents in other languages.