New object-oriented parallel pattern matching algorithm

Discussion in 'C++' started by bpontius@greateastsoftware.com, Oct 25, 2005.

  1. Guest

    The GES Algorithm

    A Surprisingly Simple Algorithm for Parallel Pattern Matching

    "Partially because the best algorithms presented in the literature
    are difficult to understand and to implement, knowledge of fast and
    practical algorithms is not commonplace."

    Hume and Sunday, "Fast String Searching", Software - Practice
    and Experience, Vol. 21 # 11, pp 1221-48

    In other disciplines, such as mathematics, the solution to a complex
    problem is frequently startling in its simplicity. In the world of
    software, this is usually not the case. At its worst, a software
    solution may simply be a road map of the programmer's confusion as he
    or she attempts to grasp the problem. At its best, this usually
    reveals the programmer's pride in being able to reproduce and
    proliferate complexity, rather than to think things through until the
    problem's innate simplicity shines through.

    In 1985, one of the tasks that I was asked to accomplish at my first
    programming job, was that of creating a user configurable terminal
    emulation program. As it happened, Dr. Dobb's Journal had just
    published an article called "Parallel Pattern Matching and Fgrep", by a
    gentleman named Ian E. Ashdown. The article presented an
    implementation, in C, of the Aho-Corasick algorithm. I read the
    article and, difficult as it was, adapted the code they published to
    create my terminal emulator.

    A few years ago, I was about to look for a job, after having spent
    several months relocating, and not programming. I decided to polish my
    C++ skills. Having used the Aho-Corasick Algorithm previously, my goal
    was to implement it, in a clean and efficient manner, using C++.
    Having seen several implementations in C, I consulted a respected
    book, Practical Algorithms in C++ by Bryan Flamig, (1999 John Wiley &
    Sons) for his implementation in C++ of the Aho-Corasick system. After
    reading this, I concluded that the algorithm did not lend itself to a
    clean or efficient implementation in C++. Flaming makes the following
    comment in his book: "The logic behind the ConstructDFA() function
    is rather difficult to explain (the author has trouble understanding it
    himself), so we leave the explanation to the original Aho-Corasick
    paper." Upon seeing this, I read their paper.

    Never having learned FORTRAN, it was only when I read their original
    paper, and discovered that their algorithm was thinking and speaking
    FORTRAN, that it all made sense to me. I was immediately reminded of
    an old programming joke (the humor of which I have never understood),
    "The determined programmer can write a FORTRAN program in any
    language". Having no desire to do this, I asked myself, "Just how
    complicated can the creation of a finite state automaton for parallel
    pattern matching be?"

    As I discovered, the problem itself is quite simple. While the
    Aho-Corasick system has been, for thirty years, regarded as the only
    way to create parallel pattern matching machines, its complexity far
    surpasses the complexity of the problem, and it is in no way
    object-oriented.

    The introduction of object-oriented programming languages has been a
    major step forward for the software development world, and it allows us
    to model our simple solution to the problem with some elegance. While
    our system lends itself to a straightforward and efficient
    implementation in most current programming languages, it is
    particularly well suited to object-oriented languages, such as C++ and
    Java. (As a matter of fact, our solution is simple enough that it can
    be implemented using three-by-five index cards)!

    I immediately formed a company, Great East Software, and applied for a
    patent for our GES algorithm. The algorithm is now patent-pending.

    The simplicity of our algorithm allows for array-based state
    transitions, which means that a variety of efficient implementations
    may easily be created. And, implemented in standard C++, the
    prototypes which we have created greatly outperform any implementations
    of the Aho-Corasick algorithm, or anything else against which we have
    been able to test.

    My question is this - does anyone know of a large software company who
    might be interested in my algorithm?
    , Oct 25, 2005
    #1
    1. Advertising

  2. Kai-Uwe Bux Guest

    wrote:
    [snip]
    > My question is this - does anyone know of a large software company who
    > might be interested in my algorithm?


    If that is your question, then your question is off-topic. Please consult
    the FAQ about what is and what is not off-topic in this group.


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Oct 25, 2005
    #2
    1. Advertising

  3. Mike Smith Guest

    wrote:

    > (As a matter of fact, our solution is simple enough that it can
    > be implemented using three-by-five index cards)!


    If that's the case, then what makes you think that you can or should
    patent it?

    --
    Mike Smith
    Mike Smith, Oct 28, 2005
    #3
  4. red floyd Guest

    Mike Smith wrote:
    > wrote:
    >
    >> (As a matter of fact, our solution is simple enough that it can
    >> be implemented using three-by-five index cards)!

    >
    >
    > If that's the case, then what makes you think that you can or should
    > patent it?
    >


    Three Words: "One Click Shopping".
    red floyd, Oct 28, 2005
    #4
  5. Guest

    Mike Smith wrote:
    > wrote:
    >
    > > (As a matter of fact, our solution is simple enough that it can
    > > be implemented using three-by-five index cards)!

    >
    > If that's the case, then what makes you think that you can or should
    > patent it?



    Unfortunately, it seems like there are more ways to abuse the patent
    system than there are to use it fairly. And in the software field,
    unfortunately, it seems that the system discourages innovation whether
    than rewarding it -- who here thinks they can write a 100-line program
    without infringing at least one software patent?

    I'd always thought this was a result of corruption seeping into the
    patent system over the years. Come to find out, the origin of patent
    law is even more corrupt than you can imagine. See
    http://righttocreate.blogspot.com/2005/10/brief-history-of-idea-monopoly.html
    for a quick summary of that.

    -- Gary
    , Oct 28, 2005
    #5
  6. mlimber Guest

    wrote:
    > My question is this - does anyone know of a large software company who
    > might be interested in my algorithm?


    Perhaps, but how much are you willing to pay for me to broker such a
    deal for you?

    Cheers! --M
    mlimber, Oct 28, 2005
    #6
  7. Guest

    Because, in thirty years, no one asked themselves, "what's wrong with
    this picture?".
    , Oct 28, 2005
    #7
  8. mlimber Guest

    wrote:
    > Because, in thirty years, no one asked themselves, "what's wrong with
    > this picture?".


    It is polite to quote the message you are responding to so others can
    follow the discussion. From your post, I could think we are playing
    "Jeopardy".

    Cheers! --M
    mlimber, Oct 28, 2005
    #8
  9. Mike Smith Guest

    wrote:
    > Because, in thirty years, no one asked themselves, "what's wrong with
    > this picture?".


    Yeah, so? It took thousands of years for someone to come along and
    invent the number zero. What if he had patented it?

    --
    Mike Smith
    Mike Smith, Oct 28, 2005
    #9
  10. Jim Langston Guest

    Re: [OT] New object-oriented parallel pattern matching algorithm

    <> wrote in message
    news:...
    > Mike Smith wrote:
    >> wrote:
    >>
    >> > (As a matter of fact, our solution is simple enough that it can
    >> > be implemented using three-by-five index cards)!

    >>
    >> If that's the case, then what makes you think that you can or should
    >> patent it?

    >
    >
    > Unfortunately, it seems like there are more ways to abuse the patent
    > system than there are to use it fairly. And in the software field,
    > unfortunately, it seems that the system discourages innovation whether
    > than rewarding it -- who here thinks they can write a 100-line program
    > without infringing at least one software patent?
    >
    > I'd always thought this was a result of corruption seeping into the
    > patent system over the years. Come to find out, the origin of patent
    > law is even more corrupt than you can imagine. See
    > http://righttocreate.blogspot.com/2005/10/brief-history-of-idea-monopoly.html
    > for a quick summary of that.
    >
    > -- Gary


    Actually, the original idea behind patents were to encourage invention. The
    though being that inventors would be more inclined to invent if they could
    actually make money off the thing they invented. If an inventor invented
    something new, they would be discouraged from doing it again if any Tom,
    Dick or Harry could come along and duplicate what they invented and sell it
    themselves out marketing them. So the inventor got an exclusive right to
    make the thing they invented for a period of time.

    For actual unique ideas, this works. Such as if someone were to actualy
    invent artificial gravity or a force field. For just new ways to do the
    same thing, this doesn't work. Such as the programmer who tried to patent
    date windowing around the turn of the century, even though date windowing
    has been used almost since the dawn of computers.
    Jim Langston, Oct 31, 2005
    #10
  11. Guest

    Jim Langston wrote:
    >
    > Actually, the original idea behind patents were to encourage invention. The
    > though being that inventors would be more inclined to invent if they could
    > actually make money off the thing they invented. If an inventor invented
    > something new, they would be discouraged from doing it again if any Tom,
    > Dick or Harry could come along and duplicate what they invented and sell it
    > themselves out marketing them. So the inventor got an exclusive right to
    > make the thing they invented for a period of time.


    If by "original idea" you mean 18th century American constitution,
    then yes, this was the reason for the compromise that resulting in
    allowing monopolies granted by congress to inventors.

    The problem is, patents didn't originate in 18th century America.
    According to the link from my last post, they've been around since the
    1400s, and the "original idea" was most definitely not to encourage
    invention. In fact, some of the earliest patents covered things like
    salt, soap, sailcloth, glass, etc. -- things that people had been
    making for centuries (if not millenia) prior to the grant of these
    patents.

    And, unfortunately, even under the US Patent system (perhaps
    particularly the US Patent system), the constitutional intent is nearly
    as much eroded now in the 21st century as it was then, in the 15th.

    -- Gary
    , Oct 31, 2005
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ricardo Batista

    dijkstra algorithm by object oriented

    Ricardo Batista, Nov 4, 2004, in forum: Python
    Replies:
    2
    Views:
    384
    Dave Benjamin
    Nov 5, 2004
  2. Replies:
    2
    Views:
    414
    Bruno Desthuilliers
    May 26, 2008
  3. rolo
    Replies:
    3
    Views:
    168
    Robert Klemme
    Apr 9, 2004
  4. Marc Bissonnette

    Pattern matching : not matching problem

    Marc Bissonnette, Jan 8, 2004, in forum: Perl Misc
    Replies:
    9
    Views:
    221
    Marc Bissonnette
    Jan 13, 2004
  5. Bobby Chamness
    Replies:
    2
    Views:
    215
    Xicheng Jia
    May 3, 2007
Loading...

Share This Page