Search code examples
algorithmparsingloggingprintfnormalizing

Looking for algorithm that reverses the sprintf() function output

I am working on a project that requires the parsing of log files. I am looking for a fast algorithm that would take groups messages like this:

The temperature at P1 is 35F.

The temperature at P1 is 40F.

The temperature at P3 is 35F.

Logger stopped.

Logger started.

The temperature at P1 is 40F.

and puts out something in the form of a printf():

"The temperature at P%d is %dF.", Int1, Int2" 
{(1,35), (1, 40), (3, 35), (1,40)}

The algorithm needs to be generic enough to recognize almost any data load in message groups.

I tried searching for this kind of technology, but I don't even know the correct terms to search for.

Solution

  • Overview:

    A naïve!! algorithm keeps track of the frequency of words in a per-column manner, where one can assume that each line can be separated into columns with a delimiter.

    Example input:

    The dog jumped over the moon
    The cat jumped over the moon
    The moon jumped over the moon
    The car jumped over the moon

    Frequencies:

    Column 1: {The: 4}
Column 2: {car: 1, cat: 1, dog: 1, moon: 1}
Column 3: {jumped: 4}
Column 4: {over: 4}
Column 5: {the: 4}
Column 6: {moon: 4}

    We could partition these frequency lists further by grouping based on the total number of fields, but in this simple and convenient example, we are only working with a fixed number of fields (6).

    The next step is to iterate through lines which generated these frequency lists, so let's take the first example.

    1. The: meets some hand-wavy criteria and the algorithm decides it must be static.
    2. dog: doesn't appear to be static based on the rest of the frequency list, and thus it must be dynamic as opposed to static text. We loop through a few pre-defined regular expressions and come up with /[a-z]+/i.
    3. over: same deal as #1; it's static, so leave as is.
    4. the: same deal as #1; it's static, so leave as is.
    5. moon: same deal as #1; it's static, so leave as is.

    Thus, just from going over the first line we can put together the following regular expression:

    /The ([a-z]+?) jumps over the moon/

    Considerations:

    • Obviously one can choose to scan part or the whole document for the first pass, as long as one is confident the frequency lists will be a sufficient sampling of the entire data.

    • False positives may creep into the results, and it will be up to the filtering algorithm (hand-waving) to provide the best threshold between static and dynamic fields, or some human post-processing.

    • The overall idea is probably a good one, but the actual implementation will definitely weigh in on the speed and efficiency of this algorithm.