[Trotil]

Практическая задачка.

Было в тексте 1000 символов.
(условимся, что все символы в тексте разные).

Удалили 300 символов.
Затем написали 100 новых символов (не встречающихся в изначальном тексте).

На сколько процентов изменился текст?

@темы: Головоломки и занимательные задачи

Comments

[Trotil]

Опорные случаи:

1) сравниваем два одинаковых текста. Текст изменился на 0 процентов.
2) сравниваем текст 1000 символов с другим текстом (любой длины и с другими символами) - текст, очевидно, поменялся на 100 % процентов. Это абсолютно два разных текста.

А дальше начинаются непонятки:

- добавили 1000 новых символов к исходному тексту. На сколько изменился текст? на 50?
- удалили 500 символов из 1000. Текст изменился на сколько? На 50 процентов?
- удалили 500 символов и добавили других 500 символов, длина текста не поменялась. Это на сколько? тоже на 50? Нелогично вроде. Цифра, наверное, должна как-то отличаться от предыдущего случая в бОльшую сторону.

[Trotil]

Что, никто не заинтересовался?

У меня есть примерный подход и вид оценочной функции, но хочется услышать и другие мнения.

[All_ex]

Trotil, Что, никто не заинтересовался?
Дык, все празднуют... ...

На сколько процентов изменился текст?
А дальше начинаются непонятки:
Требуется определение понятия "доля изменения текста"... мне кажется это особенно актуально при текстах разной длины...

удалили 500 символов и добавили других 500 символов, длина текста не поменялась. Это на сколько? тоже на 50?
тут 50 % выглядят естественным образом...

А в остальных случаях непонятно...
Если считать долю прежнего текста в новом, то:
- удалили 500 символов из 1000. - тут получится 100%
- добавили 1000 новых символов к исходному тексту. На сколько изменился текст? на 50? - тут 50...
Было в тексте 1000 символов. Удалили 300 символов. Затем написали 100 новых символов (не встречающихся в изначальном тексте). - а здесь `700/8 = 87.5%`...

[Trotil]

- удалили 500 символов из 1000. - тут получится 100%

не. 100% процентов только тогда, когда текст абсолютно другой. А если часть старого текста осталось, значит это не на 100% новый текст.
Этот новый текст на сколько-то процентов не совпадает со старым. Но не на 100.

[Trotil]

требуется определение понятия "доля изменения текста"...

надо самим придумать.

[All_ex]

Trotil, не. 100% процентов только тогда, когда текст абсолютно другой.
я считал про сохранения текста... ... то есть изменение 0% ...

[Trotil]

0% тоже не годится, т.к. с текстом произошли изменения... Он уменьшился в два раза.

[Диана Шипилова]

Он уменьшился в два раза.

Можно считать, что вторую половину текста заменили на пустые символы. Процент изменения тот же, как если бы заменили на другие символы.

[CD_Eater]

стандартный подход: измерять расстояние между текстами, определяемое количеством операций редактирования, нужных чтобы перевести один текст в другой

имеется метрика: три величины
L1 = размер первого текста (количество операций редактирования, чтобы его набрать),
L2 = размер второго текста (количество операций редактирования) и
D12 = расстояние между текстами (количество операций редактирования)
связаны неравенством треугольника,
на этой метрике можно определить коэффициент схожести текстов как величину от 0 до 1 по формуле (1 - D12/(L1+L2))
1 = одинаковы, 0 = вообще ничего общего

[Trotil]

Собственно, мой изначальный вариант очень похож на метод Дианы Шипиловой и метод CD_Eater.
Удаление текста отождествляем с заменой его на невидимый символ.

(при этом невидимому символу я приписал меньший вес, чтобы удаление символа была менее значимой операцией, чем замена символа на другой)

[Trotil]

Собственно, мой изначальный вариант очень похож на метод Дианы Шипиловой и метод CD_Eater.
Удаление текста отождествляем с заменой его на невидимый символ.

(при этом невидимому символу я приписал меньший вес, чтобы удаление символа была менее значимой операцией, чем замена символа на другой)

[Trotil]

Собственно, мой изначальный вариант очень похож на метод Дианы Шипиловой и метод CD_Eater.
Удаление текста отождествляем с заменой его на невидимый символ.

(при этом невидимому символу я приписал меньший вес, чтобы удаление символа была менее значимой операцией, чем замена символа на другой)

[CD_Eater]

а не появятся ли проблемы с несимметричностью формулы схожести, если взаимно обратные операции (вставка и удаление символа) будут иметь разную стоимость?
т.е., схожесть_текстов(текст1, текст2) != схожесть_текстов(текст2, текст1)