Since various people seem to have misunderstood the problem, I shall try to state it more precisely. What is required is a function diff :: Ord a -> [a] -> [a] -> [DiffElement a] for the type data DiffElement a = InBoth a | InFirst a | InSecond a such that given the functions f1 (InBoth a) = Just a f1 (InFirst a) = Just a f1 (InSecond a) = Nothing and f2 (InBoth a) = Just a f2 (InFirst a) = Nothing f2 (InSecond a) = Just a the following identities hold: mapPartial f1 (diff l1 l2) == l1 and mapPartial f2 (diff l1 l2) == l2 This is a well-known problem. The most helpful Web page I could find about it is here: http://apinkin.net/space/DifferenceEngine There is an algorithm known as Myer's algorithm, but obviously I want it in Haskell rather than C, and it would be nice if someone else had written it so I don't have to.
On 21-Nov-2002, George Russell <ger@tzi.de> wrote:
There is an algorithm known as Myer's algorithm, but obviously I want it in Haskell rather than C, and it would be nice if someone else had written it so I don't have to.
Would a Mercury version help? The Mercury distribution includes a Mercury version of Myer's algorithm: it's in the directory `samples/diff'. You might find it easier to translate from Mercury to Haskell than from C to Haskell. (Then again, you might not ;-) -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
G'day all. On Fri, Nov 22, 2002 at 05:13:07AM +1100, Fergus Henderson wrote:
Would a Mercury version help? The Mercury distribution includes a Mercury version of Myer's algorithm: it's in the directory `samples/diff'.
Disclaimer: I wrote the Mercury version. That particular algorithm heavily relies on destructively updated arrays, which don't map neatly onto Haskell lists. In addition, it's pretty complicated (all the caching between passes, mostly). It's also optimised for very long sequences, which may not help you here. Just for jollies, here's a Haskell version of Hirschberg's LCSS algorithm. It's O(N^2) time but O(N) space at any given point in time, assuming eager evaluation. You should be able to make diff out of this. You should also be able to find many opportunities for optimisation here. @article{360861, author = {D. S. Hirschberg}, title = {A linear space algorithm for computing maximal common subsequences}, journal = {Communications of the ACM}, volume = {18}, number = {6}, year = {1975}, issn = {0001-0782}, pages = {341--343}, doi = {http://doi.acm.org/10.1145/360825.360861}, publisher = {ACM Press}, } Cheers, Andrew Bromage module Lcss ( lcss ) where algb :: (Eq a) => [a] -> [a] -> [Int] algb xs ys = 0 : algb1 xs [ (y,0) | y <- ys ] where algb1 [] ys' = map snd ys' algb1 (x:xs) ys' = algb1 xs (algb2 0 0 ys') where algb2 _ _ [] = [] algb2 k0j1 k1j1 ((y,k0j):ys) = let kjcurr = if x == y then k0j1+1 else max k1j1 k0j in (y,kjcurr) : algb2 k0j kjcurr ys algc :: (Eq a) => Int -> Int -> [a] -> [a] -> [a] -> [a] algc m n xs [] = id algc m n [x] ys = if x `elem` ys then (x:) else id algc m n xs ys = algc m2 k xs1 (take k ys) . algc (m-m2) (n-k) xs2 (drop k ys) where m2 = m `div` 2 xs1 = take m2 xs xs2 = drop m2 xs l1 = algb xs1 ys l2 = reverse (algb (reverse xs2) (reverse ys)) k = findk 0 0 (-1) (zip l1 l2) findk k km m [] = km findk k km m ((x,y):xys) | x+y >= m = findk (k+1) k (x+y) xys | otherwise = findk (k+1) km m xys lcss :: (Eq a) => [a] -> [a] -> [a] lcss xs ys = algc (length xs) (length ys) xs ys []
Ok, here is an attempt. I don't have time to explain, but it's not Myer's algorithm. Try for example diff "abcabba" "cbabac" Gertjan Kamsteeg ================================ data In a = F a | S a | B a diff xs ys = steps ([(0,0,[],xs,ys)],[]) where steps (((_,_,ws,[],[]):_),_) = reverse ws steps d = steps (step d) where step (ps,qs) = let (us,vs) = h1 ps in (h3 qs (h2 us),vs) where h1 [] = ([],[]) h1 (p:ps) = let (rs,ss) = next p; (us,vs) = h1 ps in (rs++us,ss++vs) where next (k,n,ws,(x:xs),[]) = ([(k+1,n+1,F x:ws,xs,[])],[]) next (k,n,ws,[],(y:ys)) = ([(k-1,n+1,S y:ws,[],ys)],[]) next (k,n,ws,xs@(x:us),ys@(y:vs)) | x == y = ([],[(k,n+1,B x:ws,us,vs)]) | otherwise = ([(k+1,n+1,F x:ws,us,ys),(k-1,n+1,S y:ws,xs,vs)],[]) h2 [] = [] h2 ps@[_] = ps h2 (p@(k1,n1,_,_,_):ps@(q@(k2,n2,_,_,_):us)) | k1 == k2 = if n1 <= n2 then p:h2 us else q:h2 us | otherwise = p:h2 ps h3 ps [] = ps h3 [] qs = qs h3 (ps@(p@(k1,n1,_,_,_):us)) (qs@(q@(k2,n2,_,_,_):vs)) | k1 > k2 = p:h3 us qs | k1 == k2 = if n1 <= n2 then p:h3 us vs else q:h3 us vs | otherwise = q:h3 ps vs ----- Original Message ----- From: "George Russell" <ger@tzi.de> To: <haskell@haskell.org> Sent: Thursday, November 21, 2002 6:39 PM Subject: diff in Haskell: clarification
Since various people seem to have misunderstood the problem, I shall try to state it more precisely.
What is required is a function
diff :: Ord a -> [a] -> [a] -> [DiffElement a]
for the type data DiffElement a = InBoth a | InFirst a | InSecond a
such that given the functions
f1 (InBoth a) = Just a f1 (InFirst a) = Just a f1 (InSecond a) = Nothing
and
f2 (InBoth a) = Just a f2 (InFirst a) = Nothing f2 (InSecond a) = Just a
the following identities hold:
mapPartial f1 (diff l1 l2) == l1 and mapPartial f2 (diff l1 l2) == l2
This is a well-known problem. The most helpful Web page I could find about it is here:
http://apinkin.net/space/DifferenceEngine
There is an algorithm known as Myer's algorithm, but obviously I want it in Haskell rather than C, and it would be nice if someone else had written it so I don't have to. _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Gertjan Kamsteeg wrote:
Ok, here is an attempt. I don't have time to explain, but it's not Myer's algorithm.
[snip] Yes thanks. But it doesn't seem dramatically faster, on my test cases, than the Myers algorithm version I have developed; indeed I think it's slightly slower. However my Myers algorithm method is rather longer. I think the Myers algorithm as I've implemented it could be speeded up (maybe by a factor of 4) by using a meet-in-the-middle method as explained in Myer's paper. But I don't think I have time to implement it. The Myers algorithm as I've implemented it uses the ST monad to do array update operations while still being safe. Also I use an unboxed array. Best wishes, George
participants (4)
-
Andrew J Bromage -
Fergus Henderson -
George Russell -
Gertjan Kamsteeg