Недавно, мне пришло письмо с просьбой решить задачу.
Даны строки:
Солнце светит ярко
Ярко светит солнце
Светит солнце
Солнце светит
12345
Как видно, некоторые из строк получены путем переставления слов в других. Задача — убрать неявных злобных клонов.

Сначала я думал перебирать строки брутфорсом. То есть, сравнивать слова и прочее. Но потом Сергей Лунгу подсоветовал их сортировать. Он предложил закодировать каждое слово в строке простой хэш-функцией. Результирующий массив слов-чисел, по его задумке, нужно было отсортировать. В результате, некоторые массивы получились бы идентичными. Их и надо было удалять.
Но подумав, я решил, что идея верна, а реализация слишком мудрена. И решил не применять никаких хэш-функций, а сортировать просто слова.
Думаю, пора уже показать код, который убивает клонов.
function kill_clones($array) {
foreach($array as $str) {
#переводим строку в нижний регистр
#чтобы исключить влияние регистра
#ВАЖНО: выставить локаль в скрипте!
$lcstr = strtolower($str);
#разбиваем строку на слова
$wds = split(" ", $lcstr);
#сортируем слова
sort($wds, SORT_STRING);
#собираем строку обратно
$newstr = join(' ', $wds);
if(!isset($result[$newstr])) {
$result[$newstr] = $str;
}
}
return $result;
}
Для того, чтобы запомнить какие строки у нас уже были, я использовал ассоциативный массив, ключом которого сделал обработанную строку.
Результат работы скрипта можно увидеть, если запустить что-нибудь в этом духе:
setlocale(LC_ALL, "ru_RU.CP_1251");
$array = Array(
"Солнце светит ярко",
"Ярко светит солнце",
"Светит солнце",
"Солнце светит",
"12345"
);
foreach($array as $k=>$v) {
print "$v<br/>";
}
$result = kill_clones($array);
print "<pre>";print_r($result);print "</pre>";
foreach($result as $k=>$v) {
print "$v<br/>";
}
Надеюсь, я помог человеку, который задал мне этот вопрос по почте. А еще хорошо бы было, если бы этот нехитрый прием пригодился кому-то еще из моих читателей.
|
Vovan
18.03.2008
|
Мне этот тип тоже писал.. Прямо в коммент на блоге Зря ты их поддерживаешь. Это ж каждый теперь может пройтись по блогам и на шару сделать какую-нибудь задачу. Эта, например, смахивает на какую-то задачу для универа :) |
|
FX Poster
18.03.2008
|
да... мне тоже такое прислали в письме... и не влом решать задачи людям, которые сами нихрена не могут делать?.. |
|
18.03.2008
|
Перенеси, плиз форму комментариев вниз, а то комментариев не видно :) |
|
SHAman
18.03.2008
|
Хм... а я то думал, откуда он взялся? Ну да ладно:) Задача действительно может решаться не слишком тривиально. Поэтому пусть будет. FX Poster, по-моему, нужно сначала давать возможность прокомментировать. Допустим, есть 20 комментов. Мне тогда придется пролистать их все до низу, чтобы оставить свой. Хотя, поменять это - дело пяти минут, я все-таки не хочу менять. |
|
18.03.2008
|
А если применить морфолологические изыски, то можно будет относить, при необходимости, к клонам строки "солнце светит" и "солнце светило". Строка "солнце - светило" не будет клоном из-за тире. Хороший алгоритм, в сниппетсы. |
|
SHAman
19.03.2008
|
Kupuyc, да можно подойти к проблеме серьезней:) Про морфологические изыски я тоже писал:) |
|
user
22.03.2008
|
я её как раз сам и решил причём дней 10 назад, после того как никто не помог ... хотя автору блога спасибо + подключил функцию levinstein и проверка первых Х% слова > Мне этот тип тоже писал.. Прямо в коммент на блоге --удалено админом -- не хамите, товарищ!-- |
|
user
24.03.2008
|
твой php скрипт кстати не работает - возвращает пустую страницу и коментарии в php скриптах отделяются // или /* */ |
|
SHAman
24.03.2008
|
Мой скрипт был сначала написан мной. А потом протестирован. Потом выложен сюда методом копипаста. А потом к непу приписывались комменты и статья. Так что он работает. А комментарии отделяются не только // и /**/, но и # тоже. |
|
mihdan
26.05.2008
|
Спасибки - положу к себе в библиотеку ;) |
|
28.05.2008
|
Я бы еще на каждое слово накладывал Stemer (http://pecl.php.net/package/stem) тогда скрипт будет еще корректно обрабатывать следующее: машины ехали ехали машины ехала машина Ну и как мега вариант убирать из строки стоп слова: "на", 'в' итд. И еще: $lcstr = strtolower($str); // Убрать не нужные символы $lcstr = trim(preg_replace('#[^\-а-яa-z]+#usi', ' ', $lcstr)); #разбиваем строку на слова $wds = split(" ", $lcstr); |
|
Николай
25.01.2009
|
Нехитрый приём пригодился, спасибо :) |
by SHAman 2007