473,735 Members | 2,103 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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 4979
bp******@greate astsoftware.com 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

Oct 25 '05 #2
bp******@greate astsoftware.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******@greate astsoftware.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******@greate astsoftware.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******@greate astsoftware.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******@greate astsoftware.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******@greate astsoftware.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
news:11******** **************@ g44g2000cwa.goo glegroups.com.. .
Mike Smith wrote:
bp******@greate astsoftware.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

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
3227
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 understand is:
28
20337
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()', this.pinginterval); - but is there no way to do this without using the literal ObjectName? If I write 'this.methodName()' I get "Line 1 Char 1: Object doesn't support this property or method." in IE, and nothing happens in Firebird.
9
8595
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 (xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx). On the aspx page I have the object tag as follows:
11
9266
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 C++. I find my self sometimes, trying Object app = Object(); Object *app = Object(); Object app = new Object();
16
25419
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 the properties: mode1, mode2, and mode3. This seems simple but I can't quite figure it out... Any ideas anyone?
0
4632
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 I don't understand is:
5
2265
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 = "otherText" xmlSave("C:\folder\file.xml", mySettings) Here is the sub: Public Shared Sub xmlSave(ByVal path As String, ByVal config As
26
5690
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 several parts of the DOM, but this does not include the window object. Thank you
3
2771
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? http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Guide:Defining_Functions doesn't actually give any insight.
2
2654
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
8959
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
1
9248
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8199
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6747
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
6049
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4558
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4821
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3270
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
2187
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.