Skip to content
This repository has been archived by the owner on Aug 5, 2024. It is now read-only.

Request for code review #124

Open
tomas-nestorovic opened this issue Jan 18, 2022 · 1 comment
Open

Request for code review #124

tomas-nestorovic opened this issue Jan 18, 2022 · 1 comment

Comments

@tomas-nestorovic
Copy link

tomas-nestorovic commented Jan 18, 2022

Hi,

I yesterday ran into a problem that my diff implementation (adopted from the internet) in some cases actually doesn't work reliably.

Suppose I have a bit stream of zeros and ones, called simply "mine" (99658 bits) and "theirs" (99655 bits). These represent low-level magnetic information of two full revolutions of one and the same track on a 2DD floppy (nominally 100,000 bits).

Apart from being of different lengths (theirs being by three bits shorter than mine), there is also a difference in the middle - 34,425-th bit is different, thanks to magnetic deterioration. Otherwise, the two bit streams are identical.

image

image

image

My implementation of the diff algorithm produces the following script that transforms mine into theirs (unlike the numbering in OpenOffice Calc, the numbering of bits is zero-based, hence off by 1). The first two seem to successfully deal with the difference in the middle. The latter two fail to remove the tail three extra bits in mine.

  • insertion of 1 bit from theirs at 34424 into mine at 34424,
  • deletion of 1 bit from mine at 34424,
  • deletion of 1 bit from mine at 99646,
  • deletion of 1 bit from mine at 99650.

Because I've exhausted all my skills, I would like to ask if anyone could check my implementation of the diff algorithm and eventually fix the bug that's inside. Although I read Mr.Myers's paper "An O(ND) Difference Algorithm and its Variations," I'm not much more clever than before. The diff algorithm is implemented here (circa 100 lines of actual code):
https://github.com/tomas-nestorovic/RIDE/blob/master/Main/src/Diff.h

Edit: Attached mine.txt and theirs.txt with respective bit streams.
theirs.txt
mine.txt

MANY THANKS IN ADVANCE FOR ANY RESPONSES! :-)

@tekwizz123
Copy link

tekwizz123 commented May 22, 2022

@tomas-nestorovic This would probably be better in a form post or similar, as this isn't an issue within diff-match-patch per say but rather a request for feedback on your own project.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants