470,822 Members | 1,356 Online

# New object-oriented parallel pattern matching algorithm

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 '05 #1
10 4791
bp******@greateastsoftware.com wrote:
[snip]
My question is this - does anyone know of a large software company who
might be interested in my algorithm?

the FAQ about what is and what is not off-topic in this group.
Best

Kai-Uwe Bux

Oct 25 '05 #2
bp******@greateastsoftware.com 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
Oct 28 '05 #3
Mike Smith wrote:
bp******@greateastsoftware.com 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".
Oct 28 '05 #4
Mike Smith wrote:
bp******@greateastsoftware.com 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/20...-monopoly.html
for a quick summary of that.

-- Gary

Oct 28 '05 #5
bp******@greateastsoftware.com 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

Oct 28 '05 #6
Because, in thirty years, no one asked themselves, "what's wrong with
this picture?".

Oct 28 '05 #7
bp******@greateastsoftware.com 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

Oct 28 '05 #8
bp******@greateastsoftware.com 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
Oct 28 '05 #9

<ga**************@yahoo.com> wrote in message
Mike Smith wrote:
bp******@greateastsoftware.com 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/20...-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.
Oct 31 '05 #10
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 '05 #11

### This discussion thread is closed

Replies have been disabled for this discussion.