Как бы упростить непростое сравнение строк?

Question

[Adamos]

Есть вот такая строчка: '0012002121210212002120002101210....'
Есть таблица в БД с такими же строчками, их длина в точности одинакова.
Задача: для этой новой строки найти в базе все строки, для которых в том месте, где в одной из строк 0, достаточно часто (95%) встречается 0 в другой строке. Места, где в обеих строках не 0, не в учет.
Собственно, код на пыхе - тривиальнейший:

$total = 0;
$match = 0;
for($n = 0; $n < $size; ++$n) {
    $c1 = $cur[$n];
    $c2 = $other[$n];
    if($c1 === '0' || $c2 === '0') {
        ++$total;
        if($c1 === $c2) {
            ++$match;
        }
    }
}
$percent = ($total > 0)? round($match * 100 / $total) : 0;
if($percent >= 95) ...

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

Comments

[Алексей Уколов]

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

[Adamos]

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

[d'Ivan]

эти строки - запись в троичной системе исчисления?

[Adamos]

Капитан Пронин, нет. В сущности, интересующие данные двоичны, при подсчете разницы между 1 и 2 нет.

[Stalker_RED]

Adamos, длина строк большая?
Можно их продублировать так, чтобы двойки заменить на единицы, и сделать труЪ бинарными?

[Adamos]

Stalker_RED, да без проблем. Вопрос, что это даст.
Сравнение двух 64-битных чисел, например, мне просто НЕ НУЖНО, ни их равенство, ни неравенство ровно ничего не дают.

[Stalker_RED]

Adamos, а если сохранить бинарники, в которых заранее нули заменены на единицы, а все 1 и 2 заменены на нули?
Для новой строки числа считаем количеств нулей, уменьшаем на 5%, запоминаем.
Тогда если паре чисел сделать побитовое И - получим карту совпадающих нулей.
Подсчитываем количество единиц в этой "карте" (gmp_popcount()), сравниваем с запомненым.
Сравнивать блоками по 64 бита.

[Adamos]

Stalker_RED, в разборе ответа Wataru об этом и говорили.
И вы тоже упустили, что количество нулей нужно не только в новой строке, но и в старой тоже.
Впрочем, вы совместными усилиями навели меня на мысль, что знаменатель для процентов можно считать проще.
Нужно просто вычесть числитель из предварительно высчитанной суммы нулей в двух строках.
И высчитывать значащие биты второй раз (для определения мест, где ноль в одной из строк) не потребуется вовсе.
Да, это надо попробовать!

[Stalker_RED]

Adamos, для новой вы вычисляете эти параметры один раз, это не дорого.
А вот сравнение - дорогое, и его надо опитимизировать.
В этой схеме при каждом сравнениии надо делать только "побитовое И", и подстчет единиц.
Внезапно, есть даже встроенная функция gmp_hamdist() которая умеет сразу обрабатывать большие строки

пример со сравнением строк по 3к символов https://ideone.com/3jTFJa
Но не факт, что сравнение строк через gmp_hamdist будет быстрее, чем разбить на блоки по 64 бита и сделать обычные побитовое И и gmp_popcount

[Adamos]

Stalker_RED, ну да. hamdist тоже подходит. Вычитаем его из суммы нулей двух строк, делим пополам - получаем числитель.
В примере вы что-то напутали, должна быть строка первым аргументом и 2 - вторым. Тогда работает, выдает 5.
Надо составить бенч, пожалуй ;)

P.S. Вообще получается изящная формула процентов: (Sum0 - H) / (Sum0 + H),
где Sum0 - сумма нулей в двух строках, а H - расстояние Хэмминга.
Приятно посмотреть ;)))

[Stalker_RED]

Adamos, было вот так https://ideone.com/m5b8QL
это я потом экспериментировал, пытался понять можно ли в него скормить вместо строк число, и насколько большое. И понимает ли он другие основания, кроме 2. (вообще принимает, но число до MAX_INT и основание до 62, это есть в доках).

[mayton2019]

Adamos, автор а у тебя это учебная или практическая задача.

Интересует какая длина такого вектора и сколько datarows?

[Adamos]

mayton2019, самая что ни на есть практика, данные боевого сайта.
Габариты озвучивал уже: десятки тысяч записей, длина каждой в несколько килобайт.
Собственно, в базе-то записи разной длины, но сравниваются только одинаковые.

[mayton2019]

Adamos, десятки тысяч это сколько? 50 000 ?
Если смоделировать - то нужно чуть точнее иметь генератор таких данных.
А то можно плюс-минут 100х во времени
промахнуться.

И длина строки в несколько килобайт это сколько? 5 килобайт?

[Adamos]

mayton2019, ну пусть будет 10 тысяч записей по 1 тысяче символов.
Одна из выборок довольно близка к таким параметрам, я с ней пока и экспериментирую.

[mayton2019]

Adamos, а доля символов { 0, 1, 2 } одинаковая? По 33% примерно?

[mayton2019]

Капец Адамос мне вот это задание поперек головы стоит

для этой новой строки найти в базе все строки, для которых в том месте, где в одной из строк 0, достаточно часто (95%) встречается 0 в другой строке. Места, где в обеих строках не 0, не в учет.

Можно его как-то переформулировать твоими словами но чтоб было формально и ясно как на олимпиаде?
Даже лучше в несколько statements разбить.

[Adamos]

mayton2019, могу другими словами.
Найдите в пачке длиннющих перфокарт те, у которых с данной перфокартой совпадают дырки хотя бы в 95% от максимально возможного количества пробитых дырок (это если каждую продырявить в том месте, где дырка в другой).

[Adamos]

mayton2019, доля нулей сильно ниже, порядка 7%.
В предыдущих комментариях я ее неверно оценивал, а тут пришлось подсчитать. Глазомер подвел ;)

[mayton2019]

Adamos, блин. Чего-то 7 % это совсем грустно.

И еще одно упрощение. Нас ведь другие символы не интересуют. Тоесть можно вот это

001200....

заменить на

00**00....

и суть задачи не меняется. Верно?

[Adamos]

mayton2019, я добавил ответ с собранным по обсуждению решением. Посмотрите, там это тоже упоминается.

[mayton2019]

Adamos, ну шикардос. Только смотри чтоб ты единички с единичками там ложно не посчитал.

[Adamos]

mayton2019, расстояние Хэмминга - это количество отличий.

[mayton2019]

Adamos, так тебе-ж не это надо. Тебе надо количество совпадающих нулей.

Вот посмотри

012012
000010

здесь отличий сколько? Три. А ответ должен быть 2 потому что 2 нуля совпали. И вычитанием из суммы 2 тоже
не выходит.

[Stalker_RED]

mayton2019, потому я и предлагал предварительно инвертировать все строки (нули в единицы, все остальное в нули).
При сравнении делаем побитовое И - получаем совпавшие нули.
Осталось их сосчитать (gmp_popcount()).

Но нужно бенчмарки делать, возможно быстрее через хемминга. Хемминга, кстати, можно и внутри СУБД прогнать.

[mayton2019]

Stalker_RED, да. После преобразования исходных данных - пожалуй можно считать хемминга.
На этом можно поставить точку. Дальнейшие оптимизации - это С и ассемблер и векторизированные
команды. И map-reduce с мультипоточкой.

Answer 1

[Wataru]

Фактически у вас тут запросы, "найти строки где много нулей на этих произвольных позициях". Никакого предподсчета я тут не вижу. Можно здорово ускорить, если хранить от строк только битовые последовательности (где '0' заменяется на единичный бит). Далее каждую строку надо про AND-ить побитово с новой и подсчитать количество единичных бит. Это теооетически раз в 64-100 ускорит вычисления, если 64-битный целый тип использовать. Или еще несколько раз сверху, если использовать векторизацию. Но как это в php сделать, я не знаю.

Даже без 5% ошибок оно не оптимизируется предподсчетами. Тупо найти строки, в которых '0' вот на этих позициях - особо не наоптимизируешь.

Comments

[Adamos]

Сначала AND-ить, а потом XOR-ить. В знаменателе будет сумма того и другого.
Добавляем пересчет значащих бит.... а оно точно ускорит процесс?

[Wataru]

Adamos, ксорить-то зачем? Через and считаете нули в обеих строках. Делить надо на нули в искомой строке - их количество отдельно подсчитайте.

Будет быстрее, конечно, если хранить и обрабатывать строки как целые 64-битные числа. Потому что символы вы по одному сравниваете, а биты по 64 за раз. Естественно, подсчет единичных бит в ответе надо делать хитрее, чем проверка каждого бита. Или через таблицу на 16 бит и 4 к ней обращения, или через 8 сдвигов и сложений. Плюс читать и обрабатывать предется в 8 раз меньше байт.

[Adamos]

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

[Wataru]

Adamos, ну тогда Or-те.

[Adamos]

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

[Wataru]

Adamos, ну вы считайте 2 раза - отдельно числитель через and, отдельно знаменатель через or. У вас же в вашем коде тоже 2 проверки же.

[Adamos]

Wataru, а в чем тогда оптимизация? Только в хранении?
После которого мне нужно будет переводить данные из БД в числа для подсчетов, добавить еще две бинарные операции - и в результате все равно два раза пересчитывать каждый байт-символ. Я не уверен, что на Пыхе это не окажется медленнее того, что уже есть.

[Wataru]

Adamos, оптимизация в том, что вы 64 символа сравниваете одной процессорной операцией. Пример: вместо 4 сравнений "0001" с "1000" вы or-ите числа 14 и 7, получая 15 за одну операцию. Потом еще за 4 операции (для 64 бит) вы найдете, что там 4 единичных бита, т.е. в 4 позициях нули есть хотя бы в одной строке. Важно строки перевести в числа до запихивания в бд, если переводить в биты каждый раз, то да, никакого ускорения не будет.

[Adamos]

Wataru, подскажите, пожалуйста, как за 4 операции подсчитываются значащие биты в произвольном 64-битном числе. Навскидку не нахожу.

[Wataru]

Adamos, заведите таблицу на 32768 чисел. Для каждой позиции предподсчитайте количество единичных бит. Прибавляйте значения из таблицы для каждой четвертинки из 16 бит. А вообще, в php наверняка есть встроенная функция popcnt, которая быстро подсчитает биты.

[mayton2019]

Задача чем-то похожа на поиск центров кластеров.

[Adamos]

Wataru, 16 бит должны дать 65536 чисел. Памяти, конечно, немного, хотя Пых еще подожрет...
Да, в нем есть gmp_popcount. Но вызов функции - сам по себе дорогая операция.
В общем, наверное, об этом стоит подумать руками и посмотреть, что выйдет.

[Wataru]

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

[Wataru]

Adamos, ох, позор мне: с битами напутал. Пхп может это соптимизировать, если функция встроенная. А вообще, может какая-то встроенная процедура в БД будет быстрее работать.

[mayton2019]

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

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

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

[Vitsliputsli]

Adamos,

Да, в нем есть gmp_popcount. Но вызов функции - сам по себе дорогая операция.

Не используйте только для подсчета битов, перепишите все на gmp. Это будет быстрее, длинная арифметика для этого и создавалась.

[Adamos]

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

[Wataru]

Adamos, Кстати, может ваша БД умеет что-то с битовыми строками делать нативно. Гуглите имя БД + bitmask

[Adamos]

Wataru, там МуСкул 5.7 - себе дороже.

[Vitsliputsli]

Adamos, ну да, проглядел, что все помещается в 64бит. Подсчет кол-ва установленных битов не простая операция, вот статья с наиболее быстрыми способами https://habr.com/ru/articles/276957/

Answer 2

[GavriKos]

Ну из непосредственных.
Можно заранее для каждой пары строк вычислить нужный процент, и как только его превысили - сразу выходить из цикла сравнения посимвольного. Причем даже не процент, а количество совпадений. Это может дать прирост в ряде случаев.

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

Можно еще подумать насчет оптимизации хранимых строк. Например, заменить ненули на количество пропусков цикла. Т.е. число 0011100 записать как 00300, и уже при итерировании учитывать эту тройку как +=3.

Это так, что быстро в голову пришло

Comments

[Adamos]

Общий процент нулей близок, разбросаны они довольно хаотично, так что по половине строки выводы делать в общем случае еще рано, разве что цифры совсем околонулевые. Но они, именно за счет хаотичности, совсем низкими и не будут - вероятность совпадения 1/3 же...
Оптимизация хранения, имхо, менее критична, чем затраты на разворачивание. Длина строк не больше нескольких килобайт, много не наэкономишь.

[GavriKos]

Adamos, какое разворачивание? Вы экономите итерации циклов )

Какой процент нулей в строках? Это важно.

[Adamos]

GavriKos, навскидку нулей - 20%-30%, и длинной чередой они не идут, перемежаются.
Я, в принципе, понял идею: заменить строки количествами ненулей до следующего нуля и в одном цикле двигать два счетчика, глядя на их совпадения. Боюсь только, данные перехеривают эту оптимизацию своей неподходящей структурой. Сравнений больше, а совпадения все равно случайны.
Кабы это была карта со сплошными участками "лес-море-горы" - да, можно было бы сравнивать и так. У меня же крестики, нолики и хренолики, в которых после нолика с вероятностью под 80% - ненолик.

[GavriKos]

Adamos, Надо пробовать. Эта оптимизация делается достаточно быстро. Да, тут кнчн большая зависимость от того что там в данных. Собственно поэтому никогда и нет оптимального алгоритма (дешевого).

Количество нулей в строках предпосчитать мне кажется тоже хорошей идеей.

[Adamos]

GavriKos, фокус как раз в том, что количество нулей в строке вообще не играет роли. У двух строк с одним-единственным нулем в одном и том же месте будет 100%, у двух с половиной нулей строго в начале и строго в конце - 0%.

[GavriKos]

Adamos, влияет.
Если в изначальной строке 100 нулей, а в строке из базы - 50 - то как вы ни крутите, а 90% совпадения не получите. Как минимум на взаимном сравнении количества нулей вы можете исключать часть строк из проверок.

[Adamos]

GavriKos, я уже писал: количество нулей - 20%-30% в массе. Критической разницы нет.
Впрочем, это позволяет дешево отсечь хотя бы часть данных хотя бы в некоторых случаях - когда в одной из записей менее 95% от нулей другой. Хуже в любом случае не будет.
Да, спасибо, тут вы мне помогли.

[GavriKos]

Adamos, еще на основе ответа res2001 крутится какая то оптимизация блоками.
Пока без конкретики, но попробую расписать. Допустим блоки по 5 знаков.
Искомая строка
00100 01111 02023 0000
По блокам записываем количество нулей 4125
И строка в базе пускай
00100 01111 12023 00300
по блокам - 4114
Естественно в базе эти данные заранее просчитаны, а не на этапе поиска.
Мне кажется если сначала сравнить совпадения вот так "по блокам" то можно еще больше заранее отсеять строк. Конечно оставшиеся строки придется "уточнять" полным перебором - но это одно из направлений оптимизации - заранее отсеять часть данных.

Не уверен на 100%, надо пробовать

[Adamos]

GavriKos, опять же - не те данные. Если бы они шли монотонно и часто повторяясь - да, тут наложение 4 из 4 позволило бы считать поменьше. Но у меня чаще всего будет 1-2 из 4, которые ничего не дают. Ну, 0 из 4 тоже довольно вероятен... но все равно, подозреваю, такая оптимизация больше запутает, чем упростит. И уж на уровне базы, без перебора, точно ничего не позволит определить.

Answer 3

[res2001]

Если в отдельной таблице базы хранить еще и предварительно посчитанные количества нулей для каждой позиции во всех строках, то задача сократится до 1 прохода по символам новой строки.
При добавлении/удалении строк, надо будет модифицировать и таблицу с количеством нулей.

Comments

[Adamos]

Боюсь, тогда задача сократится до "где взять столько памяти". Умножаем десятки тысяч записей на тысячи нулей в них - получаем сотни миллионов записей в этой таблице. Добавляем к этому, что в подсчете нужны все нули не только новой строки, но и сравниваемой, только не сумма, а пересечение... впрочем, это еще можно оптимизировать. Но вот запрос-то к такой базе вы как себе представляете? SELECT record_id, COUNT(1) FROM positions WHERE number IN (тысячи чисел) GROUP BY record_id ? По стомиллионной таблице? Смело...

[Wataru]

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

[Adamos]

Wataru, я так понял, что как раз каждый ноль и предполагается переписать отдельной строчкой в базу ;)

[Wataru]

Adamos, а, и запросом к бд что-то сгруппировать? Да, выглядит медленнее решния в лоб.

[res2001]

Adamos, Wataru, Ну да, облажался. С устатку не до конца въехал в задачу.
В итоге с Хэммингом классная идея.

Answer 4

[Adamos]

Попробовал составить бенчмарк для сравнения текущего... эм... сравнения с предложенными методиками.
Данные - тысяча строк по тысяче символов. По сравнению с исходными данными в строках 2 заменены на 1, чтобы было более бинарно, но это все равно строки. Каждая строка сравнивается с каждой, кроме себя, итого почти миллион итераций.
Старый код, который в вопросе, крутил эти данные 10,3 секунды.
Новый код - 0,5 секунды:

$h = gmp_hamdist(
    $firstGmp, // gmp_init первой строки вынесен за цикл
    gmp_init($other, 2)
);
$sum = $zeroes[$n1] + $zeroes[$n2]; // подсчитанные до цикла количества 0 в строках
$percent = round(($sum - $h) * 100 / ($sum + $h));
if ($percent >= 95) { ...

Результаты идентичны. Собственно, только две строки из этой тысячи совпали на 96%, остальные - менее.
Проверка, можно ли исключить из сравнения строки по общему количеству нулей, показала, что отсеивается менее 3%. Такие данные, да...

Благодарю поучаствовавших в дискуссии и отдельно Stalker_RED - за практически готовое решение, причем "малой кровью".