Про diff

okunek

Есть два файла, на которые я натравливаю diff:

1 2 3 a b c d 5 6 7 a b c d e f 8 9 0 c d e f

1 2 3 m n o 5 6 7 p r s t 8 9 0 u v x z

Вывод diff-а:

$ diff 1.txt 2.txt

4,7c4,6

< a

< b

< c

< d

---

> m

> n

> o

11,16c10,13

< a

< b

< c

< d

< e

< f

---

> p

> r

> s

> t

20,23c17,20

< c

< d

< e

< f

---

> u

> v

> x

> z

Мне нужно так реализовать свой diff (точнее, это будет больше подходить на patch который не будет зависеть от номеров строк. Если мой дифф выдаст что-то в духе "find 'abcd' and replace to 'mno'", то он заодно найдет 'abcdef', заменит начало и получится 'mnoef', что будет ошибкой. С алгоритмом поиска общей подпоследовательности проблем нету, а вот как сделать независимость от номеров строк, в голову не приходит. Тут главное как раз то, что поиск (в данном случае) abcd не закончится пока по всему файлу эти abcd не найдутся и не заменятся.

okis

а если abcd сначала заменяется на def а потом на fgh? Тогда твой дифф должен говорить "заменить abcd на def 1 раз", "заменить abcd на fgh 1 раз".

okunek

Я вижу тут выход в добавлении к abcd еще одной буквы, чтобы отличить от других abcd. Но вот общего алгоритма не вижу.
И нельзя сказать "заменить 1 раз".

okunek

Я начинаю думать, что неправильно понял условия своей задачи, так что напишу её сюда:
Description
Create a console program that can perform the following operations:
• generate a change set file CAB for any given pair of text files (TA, TB)
• apply a given change set file CAB to an input file TX and produce the target file TY.
NOTE: when applied to the input file TA the change set file CAB must produce the original file TB
Detailed specification
1 Files TA and TB are plain ANSI charset text files (ordered collection of lines delimited by ‘\n’ character or ‘\r\n’ character combination).
2 The change set file CAB should contain human readable instructions to convert file TA into file TB. It is part of your work to design your own specification of the conversion instructions and change set file format.
3 The conversion instructions should work with whole lines (do not refer to words or symbols inside a line). Lines that differ at least in one character should be considered different (treat differences in whitespace as significant).
4 The conversion instructions must be bound to the surrounding lines context (SLC). It is not allowed to bind conversion instructions to absolute or relative line numbers.
5 Each SLC in CAB must identify the lines being added, deleted, or modified uniquely in the scope of change set CAB if it is applied to the source file TA. In other words, applying the change set instructions from CAB to the original file TA must never be ambiguous.
6 The program must allow applying the change set file to any text file if the contents of the text file are compatible with the contexts found in the change set file. Otherwise the error description should be printed out to the console. The two basic types of errors are: “required context not found” and “change set applying is ambiguous”.
Что здесь означает 5-е условие? Мне кажется, что это как раз условие правильного разруливания множественного "abcd", как я описал.

hwh2010

думаю, они считают что надо писать инструкции вида "замени a b c d на m n o между 3 и 5"
6 условие означает, что если 3 a b c d 5 встретилось в файле более 1 раза, либо ни разу, то надо выдавать соотв. ошибки
5 условие означает, что на исходном тексте этих ошибок быть не должно

ppplva

От тебя требуют unified diff без номеров строк, который можно однозначно приложить к исходному файлу. То есть просто для каждого чанка нужно взять достаточно окружающих линий, чтобы он был уникальным в TA.
Имхо, условию удовлетворяет CAB = TB.

123anna

Ну типа надо запоминать контекст вокруг каждой правки. Не формализовано, сколько этого контекста надо запоминать: если много, то размер CAB-файла увеличится и большой процент документов будут “required context not found”; если мало контекста, то высока вероятность пропатчить что-то не то.
В пункте 5 сказано, что ты обязан сгенерить патч, который будет однозначно применяться на ТА (если возникают неоднозначности, надо увеличить SLC). А уже на других документах прога имеет право заявить о неоднозначности.
Важно уточнить такой момент: нельзя закладываться на относительный порядок правок, т.е. SLC разных правок могут идти в любом порядке в ТХ. Если же закладываться на порядок можно, то задача очень сложная

pitrik2

бррр
или меня глючит или эта задача уже была?
ты ее откуда взял?
никак не вспомню, в какую-то компанию что ль ее давали решать как дз перед собеседованием

pitrik2

Ну типа надо запоминать контекст вокруг каждой правки. Не формализовано, сколько этого контекста надо запоминать: если много, то размер CAB-файла увеличится и большой процент документов будут “required context not found”; если мало контекста, то высока вероятность пропатчить что-то не то.

контекст вокруг запоминают и Eclipse и IDEA когда патч выдают
токо они собаки разное кол-во контекста заменяют
мне как-то приходилось 2 патч файла сравнивать - в результе ихние 2 патча замучаешься диффить

apl13

Если мой дифф выдаст что-то в духе "find 'abcd' and replace to 'mno'", то он заодно найдет 'abcdef', заменит начало и получится 'mnoef', что будет ошибкой. С алгоритмом поиска общей подпоследовательности проблем нету, а вот как сделать независимость от номеров строк, в голову не приходит.

Ну как. Именно, что для нахождения нужного вхождения заменяемого куска нужно будет взять столько строк контекста спереди и сзади, чтобы не перепутать с другими.
В твоем примере, то есть, инструкции такие: "abcd в '3abcd' заменить на mno, abcdef заменить на prst, cdef в '0cdef' заменить на uvxz".
Если бы было "abcd456123abcd456123abcd456789 -> abcd456123efgh456123abcd456789", то правильная инструкция - что-то вроде "[3]abcd[4561] -> efgh". Контекст - [3] и [4561].

okunek

Всем спасибо.
Как раз с алгоритмом налепить контекст и вышли трудности.
Пока сделал перебором. Более быстрое и лучшее в голову не приходит.