|
I don't know... it sounds similar to what I'm doing, which only reduces the memory footprint, not the complexity of the algorithm. I expect it's still O(mn), but I'll give it another read.
|
|
|
|
|
of course the calculations are O(mn), each matrix element needs some (simple) calculations. If you don't like that (your original question was about memory foot print, not calculations), you shouldn't be using Levinshtein at all; I've never used it myself as I consider it too much trouble to get an estimated difference between strings. That is why I suggested some alternatives. Tokenizing would save both cycles and bytes, the stochastic approach probably only saves bytes, not cycles, as it needs a lot of string scanning.
|
|
|
|
|
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)
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
