|
I was merely stating that I don't think the page is correct when it says the stated algorithm is O(min(n,m)) .
Anyway, I've had an idea of a different technique forming in my head, but before I try it I wanted to find out what other Code Projectors had used.
|
|
|
|
|
it is O(min(n,m)) in space, and that is what Wikipedia said. The computational effort remains quadratic no matter what.
|
|
|
|
|
I didn't realize that Big-O could be used for space.
|
|
|
|
|
You could use Big-O notation for any cost function you choose; time is the most popular one obviously.
|
|
|
|
|
PIEBALDconsult wrote: Code Projectors LOL. I like that. I'm gonna have to remember that and use it.
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braun
|
|
|
|
|
|
The French article in Wikipedia points to two references that should be of interest to you: http://fr.wikipedia.org/wiki/Distance_de_Levenshtein[^]. Check the Notes et réferences.
These describe implementations that are faster than O(NM) when you bound the number of differences.
|
|
|
|
|
Great link. I seldom see a regional wikipedia page offering more or better information than the English one does.
BTW: the work by Myers is what Nick Butler[^] started from when creating his entry for the lean-and-mean competition[^] two years ago. However IMO it is overkill for what PIEBALD is aiming at.
|
|
|
|
|
and a great algorithmician
Well, from the little info provided by PIEBALD, it is hard to figure out what he needs.
|
|
|
|
|
YvesDaoust wrote: a great algorithmician
YvesDaoust wrote: it is hard to figure out what he needs
he wants the codez.
|
|
|
|
|
Shouldn't be a big deal to find source code of a good diff utility.
|
|
|
|
|
I'm not looking for a diff utility, as stated in my post I'm just looking for a more efficient distance calculation.
|
|
|
|
|
Hey! I'm standing right here, I can hear you!
|
|
|
|
|
I'll give it a look later. Merci.
|
|
|
|
|
You can also have a look at
"A faster algorithm computing string edit distances, William J. Masek, Michael S. Paterson, Journal of Computer and System Sciences, Volume 20, Issue 1, February 1980, Pages 18-31."
It has an O(n^2/log(n)) behavior.
There are faster algorithm for approximate Levenshtein distance computation.
|
|
|
|
|
YvesDaoust wrote: for approximate Levenshtein distance computation
Approximate isn't good enough.
|
|
|
|
|
Hi, i'am a researcher in computer vision system (Electronics Engineer by profession) designing a system capable of out performing the current state of the art vision system. OpenCV 2.2 did not impress me, vision by machines seems 2 lag behind the simplest animal u can think of (like a cat or something else). i think computers are powerful enough 2 handle vision nearly as good as humans. Why are the state of art vision systems very task specific and not as robust as they should be?any suggestions?
|
|
|
|
|
Let's see your system and then we can judge.
|
|
|
|
|
Well first i have 2 deal with patent issues plus i'am writing a journal on it, i'have written a proprietary vision library and will be ready 2 show my system 2 the world when all the legal issues are done and when i finalise the design. these legal issues make innovation very difficult
|
|
|
|
|
BCDXBOX360 wrote: i'am designing a system capable of out performing the current state of the art vision system.
BCDXBOX360 wrote: these legal issues make innovation very difficult
You seem to have two conflicting statements here.
|
|
|
|
|
Richard MacCutchan wrote: You seem to have two conflicting statements here.
maybe i was supposed to write that ,legal processes of getting patents and other rights to an invention discourages innovation but does not make it impossible.
|
|
|
|
|
I rather meant that, having claimed that you were going to create a state of the art system that would beat anything currently available, you are now saying that you cannot do it because of the difficulty of getting a patent. That sounds like an excuse not a reason.
|
|
|
|
|
Richard MacCutchan wrote: I rather meant that, having claimed that you were going to create a state of the
art system that would beat anything currently available, you are now saying that
you cannot do it because of the difficulty of getting a patent. That sounds like
an excuse not a reason.
okey lets forget about the patent issues for now, i was initually worried about ideas being stolen, but right now as i write this i'am sitting in front of a lap-top with a vision-library (designed and coded by me) capable of out-performing the current state of the art vision systems. (i'am just optimizing the library and doing some final toughes)
|
|
|
|
|
BCDXBOX360 wrote: i'am sitting in front of a lap-top with a vision-library (designed and coded by me) capable of out-performing the current state of the art vision systems.
In that case I'll go back to my first comment: "Let us see it in action and then we can judge.".
|
|
|
|
|
Richard MacCutchan wrote: In that case I'll go back to my first comment: "Let us see it in action and then
we can judge.".
okey i will make a video presentation as soon as i finish optimizing the library
|
|
|
|