similar_text для array или как оставить логически уникальные строки в массиве

Klaus

SEO Cthulhu
similar_text для array или как оставить логически уникальные строки в массиве

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

т.е. необходимо справнить каждую строку с каждой, и если процент совпадения превышает скажем 80%, то оставить только одну(какую из них пока не важно на данном этапе)

вот что у меня получилось:
PHP:
$array1 = array("некий", "массив", "строк");
$array2 = $array1;
foreach($array1 as $key=>$value) {
   foreach($array2 as $k=>$val) {
      similar_text($array1[$key], $val, $prc);
      if($key != $k && $prc > 80) {
         $array2[$k] = ""; // unset нельзя - потеряем совпадение ключей
      }
   }
}

print_r($array2); // массив с логически уникальными строками
но.... при кол-ве значений в массиве более 500 (как у меня) - данный пример очень долго исполняется.
Помогите, пожалуйста, улучшить пример или направить на путь истинный :)
 

untied

Сдвинутый новичок
Сравнивай не два массива, а попарно элементы одного массива. Все равно будет два вложенных цикла. Сравниваем так:

1-й проход:
0-й элемент с 1-м, 2-м, 3-м, ... последним

2-й проход:
1-й элемент с 2-м, 3-м, 4м, ... последним

и т.д.

N-й проход:
(N-1) элемент с N-ым (последним)
 

Klaus

SEO Cthulhu
спасибо, получилось так:
PHP:
$array = array();

$num = count($array);

for($i=0; $i < $num; $i++) {
	for ($u = $i+1; $u < $num; $u++) {
	    if(isset($array[$i]) && isset($array[$u])) {
			similar_text($array[$i], $array[$u], $prc);
			if ($prc > 80) unset($array[$u]);
		}
	}
}
ситуация улучшилась, но не кардинально.
что можно еще улучшить?
 

untied

Сдвинутый новичок
Более быстрого алгоритма попарного сравнения элементов массива нет. Разве что есть вариант проведения сравнений во время формирования самого массива. То есть если сопоставления нашлись, то новый элемент не добавляется, а если не нашлись -- добавляется.
И я бы не делал так лихо unset() с элементами массива во время его сканирования! Отбрасываемые элементы лучше как-либо помечать и удалить уже после завершения циклов.
 

Klaus

SEO Cthulhu
Автор оригинала: untied
И я бы не делал так лихо unset() с элементами массива во время его сканирования! Отбрасываемые элементы лучше как-либо помечать и удалить уже после завершения циклов.
т.е. проверка, что я делаю
PHP:
if(isset($array[$i]) && isset($array[$u]))
- только замедляет работу? ок, спасибо, счас попробую просто присвоить пустую строку.
 

untied

Сдвинутый новичок
Originally posted by Klaus
т.е. проверка, что я делаю
PHP:
if(isset($array[$i]) && isset($array[$u]))
- только замедляет работу? ок, спасибо, счас попробую просто присвоить пустую строку.
Насчет сильного замедления не знаю... Но вот делать "дырки" в массиве когда происходит многократный проход по этому массиву не стоит. Это просто совет на будущее: непонятные ошибки полезут. :cool:
 

Klaus

SEO Cthulhu
мм.. визуально similar_text отнимает больше времени, чем isset.. такс, где-то были Димины часики

-~{}~ 11.01.05 16:34:

в любом случае, этот проход лучше, чем мой первый монстр..
спасибо за помощь!
 

Wicked

Новичок
ИМХО вцелом не очень корректная задача, т.к. по такому условию нельзя сформировать классы "почти одинаковых" слов, чтобы потом из каждого такого класса брать по одному представителю.

Пример: если у нас есть 3 записи в этом массиве, удовлетворяющие этим условиям:
similar_text($a, $b) > 80
similar_text($b, $c) > 80
similar_text($a, $c) < 80
то в зависимости от последовательности их сравнения, от них могут остаться, как одна запись, так и две.
 

untied

Сдвинутый новичок
Мне кажется, что наиболее оптимальный вариант -- это проводить сравнения слов во время формирования массива. Причем формировать нужно двумерный массив, где в каждой строчке хранятся схожие варианты одного слова.
То есть берем очередное новое слово, сравниваем попарно с нулевым элементом каждой из строк двумерного массива. Если совпадение обнаружено, то добавляем слово в конец найденной строчки. Если совпадений нет, то формируем новую строчку в массиве.
При таком подходе число сравнений будет минимальным. Причем в конце работы получатся более-менее логично отсортированные слова, с которыми потом можно произвести некие операции (к примеру, выбрать из каждой строчки по одному слову, наиболее отвечающему неким критериям).
 

Profic

just Profic (PHP5 BetaTeam)
Я в свое время реализовывал примерно такой алгоритм (задача правда была немного другой - найти во всех строках максимально похожую на заданную, строки на ангельском, список строк в mysql)
1) создаем временную таблицу с SOUNDEX по данному списку
2) для каждой входящей строки делаем запрос в эту временную таблицу сравнивая SOUNDEX-ы, если строка одна - используем ее
3) если строк больше чем одна, то применяем similiar_text для пар состоящих из заданной строки и каждого результата, если результат только одной строки > N используем ее - иначе отдаем на растерзание пользователю :)
Вот. Может чем поможет :)
 

Wicked

Новичок
Я как раз про это и говорил, что тут нету правильного способа разбить все множество слов на массив массивов. Но если его Klaus'а это устраивает, то пусть делает так.

Klaus, а можешь рассказать поподробней о твоей задаче?
 

Silent

Новичок
А если делать первый цикл по оригинальному массиву и постепенно заполнять другой массив? При этом сравнивать нужно со вторым массивом. То есть идем по первому массиву и сравниваем с каждым элементом второго. Если нашли похожее, то отбрасываем, иначе помещаем во второй массив. В наихудшем случае (все элементы разные) получим примерно ту же сложность, что и в твоем алгоритме. Но если все элементы одинаковые, то в итоге мы просто сравним все элементы первого массива с одним единственным элементом второго массива.
 

Klaus

SEO Cthulhu
сорри, увлекся дальнейшим написанием программы...

задача очень простая:
вырезать только наиболее(!) похожие строки по написанию(!),
типа:
1. sneg byl belym i bylo holodno
2. sneg byl belym i bylo prohladno
то одно убираем, а если так
1. sneg byl belym i bylo holodno
2. bylo holodno i sneg byl belym
оставляем оба

отсюда и такой высокий устраивающий процент совпадений
 

Wicked

Новичок
1) Еще немного можно оптимизировать, если сначала либо делать array_unique(), либо сами слова хранить в ключах (а не в значениях) массива и сначала проверять на точное соответствие.

2) предположим, что нас интересует 80% совпадений букв. Тогда, например, 5и-буквенные слова нужно сравнивать только со словами длины 4,5 и 6. В этом случае можно предварительно слова из одномерного массива перевести в двумерный массив по длинам. Я точно не знаю, как с similar_text() работает с длинами строк, но идея надеюсь понятна.

3) Я бы использовал levenstein();
The Levenshtein distance is defined as the minimal number of characters you have to replace, insert or delete to transform str1 into str2. The complexity of the algorithm is O(m*n), where n and m are the length of str1 and str2 (rather good when compared to similar_text(), which is O(max(n,m)**3), but still expensive).
 

Klaus

SEO Cthulhu
levenshtein к сожалению не подходит из-за ограничения на длину строки в 255 символов.

array_unique - смысла нет делать, имхо, две операции получается вместо одной, т.к. 99.9% строк уникальны с точки зрения array_unique
 

Wicked

Новичок
Ну а еще более глобально можешь задачу описать?
Может было бы лучше для сравнения строк (тем более если они большие), разбивать строки на слова и работать на этом уровне. Если тебя, например, не интересуют опечатки внутри слов, то из работы со строками:
1. sneg byl belym i bylo holodno
2. sneg byl belym i bylo prohladno
получилась бы работа с такими массивами:
1. array(1,2,3,4,5,6)
2. array(1,2,3,4,5,7)
 
Сверху