473,226 Members | 1,697 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 4935
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 thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 1 by: Bijay Kumar | last post by: Hi Guys, I was going through the source code of Object.cs in rotor. What I found is Equals() implemented as follows: public extern virtual bool Equals(Object obj); What I don't... 28 by: Daniel | last post by: Hello =) I have an object which contains a method that should execute every x ms. I can use setInterval inside the object construct like this - self.setInterval('ObjectName.methodName()',... 9 by: Keith Rowe | last post by: Hello, I am trying to reference a Shockwave Flash Object on a vb code behind page in an ASP.NET project and I receive the following error: Guid should contain 32 digits with 4 dashes... 11 by: DrUg13 | last post by: In java, this seems so easy. You need a new object Object test = new Object() gives me exactly what I want. could someone please help me understand the different ways to do the same thing in... 16 by: sneill | last post by: How is it possible to take the value of a variable (in this case, MODE_CREATE, MODE_UPDATE, etc) and use that as an object property name? In the following example I want 'oIcon' object to have... 0 by: Bijay Kumar | last post by: Hi Guys, I was going through the source code of Object class (Object.cs in rotor). What I found is Equals() implemented as follows: public extern virtual bool Equals(Object obj); What... 5 by: Matthew | last post by: I have a nice little Sub that saves data in a class "mySettings" to an XML file. I call it like so: Dim mySettings As mySettings = New mySettings mySettings.value1 = "someText" mySettings.value2... 26 by: yb | last post by: Hi, Is there a standard for the global 'window' object in browsers? For example, it supports methods such as setInterval and clearInterval, and several others. I know that w3c standardized... 3 by: User1014 | last post by: A global variable is really just a property of the "Global Object", so what does that make a function defined in the global context? A method of the Global Object? ... 2 by: Ralph | last post by: Hi I don't understand why it's not working: function schedule(imTop){ this.tdImagesTop = imTop; } schedule.prototype.selectEl = function() { alert(this.tdImagesTop); 0 by: VivesProcSPL | last post by: Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for... 3 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In... 0 by: jianzs | last post by: Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from... 0 by: abbasky | last post by: ### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method... 2 by: jimatqsi | last post by: The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art... 2 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE... 0 by: fareedcanada | last post by: Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like... 0 by: stefan129 | last post by: Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific... 0 by: MeoLessi9 | last post by: I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....