Форум PHP

В папке есть некое количество файлов, каждый из которых характериузуется набором слов в виде буквенно-цифровых обозначений. Например, первый файл характеризуется словами a1b, bcde, klm, bcde, а второй характеризуется словами ssr, klm, s9b.

Количество слов в характеристике файлов может отличаться, а некоторые слова могут встречаться у разных файлов (в примере слово klm).

Кроме того, одно и тоже слово может быть в названии одного файла несколько раз (в примере слово bcde).

Слова-характеристики не являются матрицей, то есть их положение для целей, о которых я скажу далее, не влияет на характеристики файла (например, файл с характеристиками a1b, bcde, klm, bcde будет иметь те же свойства, что и файл с характеристиками bcde, bcde, a1b, klm).

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

Если при выборе сравнивать все файлы массива попарно кайжый с каждым, то критерием выбора будет выражение

Nобщ * 100 / (N1 + N2) < заданный процент.

Где:
Nобщ - количество слов, общих для данной пары файлов.
N1 + N2 - сумма слов этой пары файлов.

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

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

Не очень понятно, как файлы называются, если не сложно приведите названия первых 20 файлов директории?

С именами файлов тут логической связи нет - я их нумерую в порядке создания и получается 1.htm, 2.htm, 3.htm и т.д. И уже для каждого созданного файла по специальной методике (шинглов) вычисляю его характеристики. Вот и получается, файл 1.htm с характеристиками a1b, bcde, klm, bcde

а где содержатся эти характеристики? откуда можно догадаться, что файл 1.htm с характеристиками a1b, bcde, klm, bcde?

В массиве

<?php    $content[1][0] = "a1b";    $content[1][1] = "bcde";    $content[1][2] = "klm";    $content[1][3] = "bcde";    $content[2][0] = "ssr";    $content[2][1] = "klm";    $content[2][2] = "s9b";

Первая координата соответствует имени файла.
$content[1][0] - для файла 1.htm
$content[2][0] - для файла 2.htm

Вам, я так поняла, пересечение массивов надо узнать.

<?php   $content[1][0] = "a1b";     $content[1][1] = "bcde";     $content[1][2] = "klm";     $content[1][3] = "bcde";     $content[2][0] = "ssr";     $content[2][1] = "klm";     $content[2][2] = "s9b";  $count = count($content); for($i = 0;$i<$count;$i++){ $res = array_intersect($content[$i], $content[$i+1]); print_r($res); } $c = count($res); print($c); ?>

Верно, Лена, надо найти пересечение массивов. Но не соседних, а каждого с каждым. Результатов будет гораздо больше, чем массивов (может, в квадрате? При 100.000 массивов это 10 миллиардов).

Причем и это еще не всё.

На основании результатов пересечения каждого массива с каждым выбрать ТАКИЕ файлы, что бы как можно больше их число удоалетворяло требованию допустимого процента пересечения.

Вот это самая главная сложность.

Посмотрите на три массива, которые получатся.
Я добавила элемент с 3 индексом. Теперь на выходе у вас три массива - сравнение $content[1] и $content[2], первого и третьего и второго и третьего элементов массива $content

<?php   $content[1][0] = "a1b";      $content[1][1] = "bcde";      $content[1][2] = "klm";      $content[1][3] = "bcde";       $content[2][0] = "ssr";      $content[2][1] = "klm";      $content[2][2] = "s9b";    $content[3][0] = "qwe"; $content[3][1] = "a3sdf"; $content[3][2] = "vbcn3x"; $content[3][3] = "klm"; $content[3][4] = "bcde"; for($i = 0;$i<count($content);$i++){     for($n = 1;$n<count($content[$i]);$n++){     $res = array_intersect($content[$i],$content[$i+$n]); print "<pre>"; print_r($res); print "</pre>";     } } ?>

Вот это Вам надо?

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

>При 100.000 массивов это 10 миллиардов
Может, эти массивы разбить на более маленькие куски?

>На основании результатов пересечения каждого массива с каждым выбрать ТАКИЕ файлы, что бы как можно больше их число удоалетворяло требованию допустимого процента пересечения.
Вы, наверное, хотите определить релевантность.

>допустимого процента пересечения
допустимый процент от чего считается?

Добпустимый процент при парном сравнении учитывается так:

Nобщ * 100 / (N1 + N2) < заданный процент.

Где:
Nобщ - количество слов, общих для данной пары файлов.
N1 + N2 - сумма слов этой пары файлов.

Массив в коде - тот же самый.

<?php for($i = 0;$i<count($content);$i++){      for($n = 1;$n<count($content[$i]);$n++){     $res = array_intersect($content[$i],$content[$i+$n]);      //Nобщ = $res;     //N1 + N2 =count($content[$i])+($content[$i+$n])     if($res != '')         $rel[] = count($res)*100/(count($content[$i])+count($content[$i+$n]));     }  } print_r($rel); ?>

В массиве $rel - результат попарного сравнения.
Одного не могу понять: почему в $res оказываются пустые значения... Избавилась от них через условие if($res != ''), но если в результате пересечения массивов будет ноль... Вот над этим надо думать. Подумаю - скажу, сейчас написала, что первое в голову пришло.
В каком виде Вам нужно это все вывести на страницу?

Исходя из того, что мы вводили исходную информацию в виде двухкоординатного массива, в котором первая координата соответствует номеру исследуемого файла
$content[1][0] - для файла 1.htm
$content[2][0] - для файла 2.htm

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

>Результат желателен в виде списка этих координат, удовлетворяющих условию отбора.

Например.
Взяли мы $content[1][0] и $content[1][1]. Сравнили. 5 слов совпало. Вывели на страницу $content[1][0] и $content[1][1].
Взяли $content[1][1] и $content[1][2]. Сравнили. НИЧЕГО НЕ СОВПАЛО. НИЧЕГО НЕ ВЫВЕЛИ.
Взяли $content[1][2] и $content[1][3]. Сравнили. 6 слов совпало. Вывели на страницу $content[1][2] и $content[1][3].
В результате у нас на странице список -
$content[1][0], $content[1][1], $content[1][2] и $content[1][3].

Смысл?
Если в результате мы получаем тот же самый список.

PS и в соседних темах Вы, похоже, тоже самое решаете

Взяли мы

$content[1][0] = "a1b";       $content[1][1] = "bcde";       $content[1][2] = "klm";       $content[1][3] = "bcde";

и сравнили с

$content[2][0] = "ssr";       $content[2][1] = "klm";       $content[2][2] = "s9b";

Как видите, совпало одно слово. А всего слов 7. Процент совпадений 2*100/(4+3) = 28%. Если это больше заданной нормы, то запоминать нечего. Если это меньше заданной нормы, то запоминаем файл 1.htm

Далее сравниваем параметры записи, относящейся ко второму файлу, с параметрами, относящимися к третьему файлу. И так до конца массива, запоминая файлы, удовлетворяющие условию выборки. Последнюю запись сравниваем с первой.

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

Но это не оптимально.
Потому, что номенклатура выбранных файлов зависит от того, какой файл оказался первым в цепочке сравнения. И количество выбранных файлов от этого зависит тоже.

Более того, отобранные по цепочке файлы могут не удовлетворять условию выборки при сравнении каждого с каждым. А это уже брак в работе.

Мне хочется оптимизировать выборку таким образом, что бы в ней оказалось как можно больше файлов, удовлетворяющих условию отбора по принципу "каждый с каждым".

Собственно, это и есть основная задача.

Поняла. Вы сравниваете два файла. Если находите в них одинаковые слова - первый файл вы запоминаете, а второй просто выбрасываете. И в результате потери от того, что вы делаете - 50%. Т.е. половину результата вы вообще не учитываете.
Тогда алгоритм такой. Два файла сравнили - где-то их запомнили , наример, в элементе массива, присвоили каждому из них полученное процентное соотношение(можно его просто напололам делить, файла же два), потом сложить все и поделить на количество "встречаний" определенного файла в сравнениях.
Пример.
Сравнили 1.html и 2.html - совпало 7 слов, это, допустим, 34%. Файлу 1.html присвоили 17% и файлу 2.html присвоили 17%.
Сравнили 1.html и 3.html - ничего не совпало. Файлу 1.html присвоили 0% и файлу 2.html присвоили 0%.
Сравнили 1.html и $n.html, $n - следующий файл для сравнения. Совпало 10%. Файлу 1.html присвоили 5% и файлу $n.html присвоили 5%.
Посчитали, сколько раз мы сравнивали 1.html - в нашем случае это три раза.
Высчитали общую сумму $sum процентов для файла 1.html, поделили на число его "встречаний" в процессе сравнений, т.е. на 3. Итого (17%+0%+5%)/3.
Дальше определяем какой-то процентный порог. Если файл 1.html больше этого порога, выводим, меньше - не выводим.
Я это так понимаю.

Не обязательно в отсев идет 50 %.
Если все слова уникальны, то отсева совсем не будет.

Если пара первый-второй неуникальна, то ничего не запоминается, но и второй файл не отбрасывается. Зачем его в игнор? Он еще с третьим не сравнивался...

Я не о том. Сравнили два файла. Результат сравнения для первого мы запоминаем(допустим, выводим его в броузер), для второго - нет. Мы его просто опускаем, мы его не выбрасываем. Но именно в этой связке с первым файлом мы информацию про второй не запоминаем. Зачем тогда сравнивать?

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