Re: String Comparison
- From: Dave <davidct1209@xxxxxxxxx>
- To: programmingblind@xxxxxxxxxxxxx
- Date: Tue, 12 Apr 2011 05:55:39 -0700
I think with LCS, you're talking about polynomial time. Would hlep a
lot if you reduced the size of the inputs a bit...
On 4/12/11, Sina Bahram <sbahram@xxxxxxxxx> wrote:
> no, just examine the complexity class of LCS. I think the dynamic
> programming approach maxes out at n^3, but is usually like N^2
> plus some constant
> ? it's been a while since algorithms, and I freaking hate the LCS algorithm,
> since we had to walk through it by hand on a final.
>
> Also, keep in mind you can memoize your results implicitly using a matrix.
>
> Take care,
> Sina
>
>
> -----Original Message-----
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Ken Perry
> Sent: Tuesday, April 12, 2011 8:42 AM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: RE: String Comparison
>
>
> Nod I saw that in the stuff Jared sent out. They talk about the speed of
> that algorithm though. What's the damages if I compare something like a .5
> MB string with another is it going to take years to do unless I get a super
> computer?
>
> ken
> -----Original Message-----
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Sina Bahram
> Sent: Tuesday, April 12, 2011 8:39 AM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: RE: String Comparison
>
> You want to search for longest common substring, or more rellavently,
> longest common subsequence.
>
> There is a simple dynamic programming approach to implement LCS.
>
> Be warned that any metric of similarity will be arbitrary, so you need to
> pick what suits your application.
>
> Take care,
> Sina
>
>
>
> -----Original Message-----
> From: programmingblind-bounce@xxxxxxxxxxxxx
> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Ken Perry
> Sent: Monday, April 11, 2011 11:25 PM
> To: programmingblind@xxxxxxxxxxxxx
> Subject: String Comparison
>
>
> I am playing with something I am writing on the side and am wondering if
> someone knows of a library that does comparisons of strings or files by a
> percentage of similarity of the two strings. So for example if I pass it
> two strings it could return that they are 52 percent alike using some magic
> metric. I have some small things I wrote in AI but my AI is being rather
> stupid so I am thinking of going to something like a recursive function but
> it seems like that would take a long time to compare two files with this
> recursive function that worms its way through large strings. These strings
> could be as large as .5 mb and they could be anywhere from a 100% match to
> as low as not a match at all.
>
> So if anyone knows of a tool that does this even if it's a command line tool
> I could create files of strings if necessary.
>
> Ken
>
> __________
> View the list's information and change your settings at
> //www.freelists.org/list/programmingblind
>
> __________
> View the list's information and change your settings at
> //www.freelists.org/list/programmingblind
>
> __________
> View the list's information and change your settings at
> //www.freelists.org/list/programmingblind
>
> __________
> View the list's information and change your settings at
> //www.freelists.org/list/programmingblind
>
>
__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind
Other related posts:
