Помогите с алгоритмом

← →
ford © (2009-12-23 22:08) [0]

Всем доброго времени суток!
Подскажите, как сделать такую задачу, не могу точно сформулировать, но
например дано две строки
1. "наша мама мыла раму"
2. "любая мама иногда моет раму весной"
надо сделать из этих строк такие
1. "наша 1 мыла 2"
2. "любая 1 иногда моет 2 весной"
причем естественно за ранее неизвестно какие из слов в этих строках будут повторяться

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

← →
TUser © (2009-12-23 22:21) [1]

поиск общих подстрок называется

← →
KilkennyCat © (2009-12-23 22:24) [2]

replace

← →
TUser © (2009-12-23 22:26) [3]

Вообщем, примерно так

var CommonSubStrLength: array[1..len(Str1),len(Str2)] of integer;
begin
for all matrix element do it := 0;
for every i do CommonSubStrLength[1,i] := 1 if Str1[i] = Str2[1] or 0 overwise;
similar for CommonSubStrLength[i,1];
for every other
if Str1[i] = Str2[j] then
CommonSubStrLength[i,j] := CommonSubStrLength[i-1,j-1]
else CommonSubStrLength[i,j] := 0;
get values larger than a thresold - it is your words
replace them in Str1 and Str2;
end

← →
KilkennyCat © (2009-12-23 22:28) [4]

, а ступил, тут общее искать...
если сжать все:
слова первой строки забиваются в массив, заменяются индексами
во второй строке слова из этого массива совпадающие забиваются индексами, несовпадающие добавляются в массив.
с последующими строками тоже самое.

← →
ford © (2009-12-23 22:53) [5]

>>KilkennyCat © (23.12.09 22:28) [4]

о, спасиба :)
что то вырисовывается

← →
KilkennyCat © (2009-12-23 22:58) [6]

я так кладр оптимизировал. а потом еще по корням оптимизировал. до 1,5 мегабайт из 70 первоначальных дооптимизировал и запарился разбирать потом :)

← →
ford © (2009-12-23 22:58) [7]

млин..... а вот какже
если
"мама мыла красную раму"
"мама мыла зеленую раму"
если идти по словам то получиться
"1 2 красную 3"
"1 2 зеленую 3"

а хотелось бы
"1 красную 2"
и "1 зеленую 2"
соответсвенно где 1="мама мыла" и 2="раму"

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

← →
Petr V. Abramov © (2009-12-23 23:03) [8]

> причем естественно за ранее неизвестно какие из слов в этих
> строках будут повторяться

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

торможу :)
получается примерно такой алгоритм
1. берем слово и строки 1
2. проверяем есть ли оно в строке 2
3 если есть то добавляем к выбраному слову второе по порядку из строки 1 и вертаемся в п.2
4. если нет, то. сохраняем его в и присваиваем ему код, заменяем в строке 1 и строке 2 все что нашли на код.
5. если не конец строк 1 то переход к п.1

как думаете нормально будет?

для двух строк что угодно нормально. для более чем двух не что угодно...

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

мама мыла красную раму мама мыла зелёную раму мама помыла сферическую раму в вакууме

из всех строк создаём словарь с индексацией.
Получается
1 - мама 2 - мыла 3 - красную 4 - раму 5 - зелёную 6 - помыла 7 - сферическую 8 - в 9 - вакууме

таким образом имеем следующие наборы индексов:
1234 1254 167489

ну а дальше тупым перебором ищи общие комбинации.
Я бы как-то так делал.

Помогите с алгоритмом Найти похожие ветки