🚀 go-pugleaf

In <1glp5cINN1nm@usenet.INS.CWRU.Edu> al045@cleveland.Freenet.Edu (Gergely Tapolyai) writes:


>Setting:  A Database, where changes on a record must be kept, i.e.
>          a history of changes by storing records as an archive
>          before it changes.
>Problem:  Space limitation.  Records can be as large as 1MByte.
>          
>Solution:  Well, that is what I am looking for.  I have thought
>           of compression, keeping delta records, and finaly
>           I came uppon reverse delta records.

>Now the only thing I need is an algorithm for it.  

>Anyone out there can point me to the right direction?

I think the standard difference algorithm is the Miller-Myers algo.
It's fairly straightforward.  The article is called "An O(ND) Difference
Algorithm and its Variations" but I can't recall where it's written up; I
think somewhere in Communications of the ACM.  A more readable version
exists somewhere in Software Engineering; you might try flipping through
some indices.  Hope this helps.

                            --Orion
-- 
      Orion Auld           |Oh, Lord, won't you buy me a 486
"We are only fabulous      |My friends all use Vaxes, but they make me sick
 beasts, after all."       |I want to run Windows; it needs to run quick
 -- John Ashberry          |So Lord, won't you buy me a 486

-- 
      Orion Auld           |Oh, Lord, won't you buy me a 486
"We are only fabulous      |My friends all use Vaxes, but they make me sick
 beasts, after all."       |I want to run Windows; it needs to run quick
 -- John Ashberry          |So Lord, won't you buy me a 486