PHP.SU

Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (2): [1] 2 »   

> Описание: Весьма сложная задача сравнения
EuGen Администратор
Отправлено: 26 Июня, 2007 - 16:06:21
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Здравствуйте, создаю тему с вопросом о сравнении. Описываю ситуацию:
0. Существует таблица в БД, в которой существенным является то, что у нее есть колонка строкового типа, хранящая шаблоны для сравнения (это сравнение нужно для правильной работы скрипта, см. ниже). Эти шаблоны представляют собой обычные регулярные выражения. Например, ^[c|с|С|s][t|т|Т][a|а|А][n|н|Н] (оно отвечает строкам "сТан", "sTAN" и т.п.)
1. Существует скрипт (для ясности назовем его "поисковик"), который по введенной строке выдает либо все записи из указанной таблицы, либо сообщение о том, что ничего не найдено. При этом поиск ведется с учетом шаблона, то есть используется стандартная для MySQL функция REGEXP. Запрос в таком случае выглядит так:
SELECT * FROM таблица WHERE $search_str REGEXP prefix
Здесь prefix - поле в таблице БД, хранящее шаблон-регулярное выражение.
2. Существует еще один скрипт (для ясности назовем его "обработчик"), который по входной строке тоже делает поиск в этой же таблице, затем найденную строку обрабатывает неким образом и делает еще много чего (тут не существенно). Так вот, должна быть гарантия того, что обработчик всегда находил единственную строку в этой таблице.
3. Собственно, поисковик нужен для следующего: пользователь делает поиск по этой таблице, и, если не находится, то все хорошо, и можно в таблицу добавить эту строку (так как обычная строка тоже есть шаблон). Если нужно добавить не просто сроку, а целый шаблон.... то этим занимается администратор (потому что пользователь все равно не поймет как там с регулярными выражениями работать). В любом случае отбор с помощью REGEXP даст гарантию, что юзер если и добавит строку в эту таблицу, то все будет уникально.
4. Теперь представим себе такую ситуацию: есть уже указанный ранее мной шаблон ^[c|с|С|s][t|т|Т][a|а|А][n|н|Н], а мы введем поисковику строку "st". Так как
st REGEXP ^[c|с|С|s][t|т|Т][a|а|А][n|н|Н] есть ложь, то юзер не увидит записей из таблицы, а увидит, что записей нет и можно добавлять. Предположим, мы добавили строку st. Ну и теперь подадим обработчику на вход строку "stan". Получится, что будет найдено 2 записи в таблице, так как stan REGEXP st есть истина и stan REGEXP ^[c|с|С|s][t|т|Т][a|а|А][n|н|Н] тоже есть истина.
5. Очевидно, что избранный в пункте "1." способ проверки уникальности записей в таблице неверен. В связи с этим приходим к мысли о том, что необходимо обратное преобразование регулярного выражения. Иначе говоря, для приведенного примера нам нужно сравнить 2 регулярных выражения: вычислить нечто вроде ^[c|с|С|s][t|т|Т][a|а|А][n|н|Н] REGEXP st, где строка, стоящая слева от REGEXP, должна пониматься именно как регулярное выражение. Очевидно так же, что аналогом такой задачи есть задача: найти множество строк, соответствующее нужному регулярному выражению, сделать "входная строка" REGEXP строка_множества (то есть для каждой строки полученного множества).
Чтобы было понятнее, приведу как это выглядит для приведенного примера:
а)"Восстанавливаем" множество строк, которое соответствует ^[c|с|С|s][t|т|Т][a|а|А][n|н|Н]. Это будет ("stan", "staN", "stAn", "stAN", "sTan", "sTaN", "sTAn", "sTAN", "Stan", "StaN", "StAn", "StAN", "STan", "STaN", "STAn", "STAN", ...) я нарочно не привел варианты для русской раскладки, так как это очень удлиннит запись.
б)Сделать "st" REGEXP "stan", ... , "st" REGEXP "STAN" (для каждого элемента множества). В итоге получим правильный ответ.
6. Очевидно так же что метод, который изложен в "5" в ряде случаев нереализуем, ибо есть регулярные выражения, которым соответствует бесконечно число строк. Всвязи с этим встает задача сравнения 2-х регулярных выражений, которую я описал. (Для приведенного примера ее решение значит, что когда юзер вводит поисковику строку "st", показывается запись БД, в которой в шаблоне записано "^[c|с|С|s][t|т|Т][a|а|А][n|н|Н]").
7. Постарался как можно подробнее изложить проблему, если кто то может помочь - рад любой информации по этому вопросу. Всем заранее спасибо.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok
Отправлено: 27 Июня, 2007 - 13:12:24
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)




^[c|с|С|s][t|т|Т][a|а|А][n|н|Н]$


-----
Truly yours, Sasha.
 
My status
 Top
EuGen Администратор
Отправлено: 27 Июня, 2007 - 13:24:43
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Спасибо за ответ, но скорее всего, нет, так не подойдет, ведь тогда и само регулярное выражение в БД будет задавать не тот набор строк, который он задавал раньше, и, соответственно, "обработчик" будет работать неверно. (Точнее, результаты его работы нас не устроят).


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok
Отправлено: 27 Июня, 2007 - 15:42:06
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)




st по регулярке выше не пройдёт. stan пройдёт.
под st будет ^[c|c|S|s][t|T|T|т]$ и стан под неё не пройдёт.


(не копируй ту что под st. Там половину букв русских)


-----
Truly yours, Sasha.
 
My status
 Top
EuGen Администратор
Отправлено: 27 Июня, 2007 - 15:47:40
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




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


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok
Отправлено: 27 Июня, 2007 - 16:14:24
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)




Пользователь вводит st
скрипт проверяет и видит что нет в базе строки с соотвтетсвующей строкой (тоесть нет регулярки соотвтетсвующей st)
Предлагает создать.
Пользователь соглашается.
и скрипт создаёт регулярку, или отправляет сообщение администратору чтоб тот в ручную её создал\n\n(Добавление)
Можно для интереса создать такой конкурс на написание того скрипта
который превращает st в ^[c|c|S|s][t|T|T|т]$
Только понадобится таблица транслитерации.
Тоесть что надо писать для букв типа j / ь / й / q

Оцениваются скорость выполнения, ясность, длинна


-----
Truly yours, Sasha.
 
My status
 Top
EuGen Администратор
Отправлено: 27 Июня, 2007 - 16:36:41
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Да, а если я хочу чтобы обработчик реагировал только на "st" ... а не на "sT" скажем или "ST" (ну и т.п.) ... Если мне ввести не строку а целое регулярное выражение, то я таким образом делаю занятым еще много чего, чего мне делать занятым не надо (более того - в соответствии с логикой даже и нельзя). Это, конечно, один из выходов, но только вот, к сожалению, не совсем то, что надо.
Как бы там ни было, спасибо Вам огромное за ответы! (больше что то никто кроме Вас не отвечает)
вероятно конечно просто "^[ s ][ t ]$" нам поможет. (пробелы для верного отображения)
Да, и кстати, еще замечу, что я писал, что решение задачи поставленной значит, что при поиске юзером через поисковик строки "st" и наличии в базе ^[c|с|С|s][t|т|Т][a|а|А][n|н|Н], должна находиться запись, соответствующая этому выражению. А предложенное решение оптимизирует поиск для обработчика, а не решает задачу для поисковика.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok
Отправлено: 27 Июня, 2007 - 23:49:31
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)




тогда обработчик пусть работает с регулярками
^[c|с|С|s][t|т|Т][a|а|А][n|н|Н]$
а поисковик через WHERE 'regexpfield' LIKE '[c|с|С|s][t|т|Т]%'


-----
Truly yours, Sasha.
 
My status
 Top
EuGen Администратор
Отправлено: 28 Июня, 2007 - 09:12:00
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Спасибо, но проблема тут в том, что как мне решить, когда поисковику искать через LIKE, а когда - через REGEXP .. (сейчас все шаблоны считаются регулярными выражениями, то есть поиск всегда через REGEXP идет).


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok
Отправлено: 28 Июня, 2007 - 09:18:18
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)




Никто кроме меня не отвечает потому что не очень понятен смысл задачи. Да и мне тоже не очень..

--

Цитата:
когда поисковику искать через LIKE, а когда - через REGEXP

Всегда через LIKE как в моём предыдущем посте.
Тогда поисковик по запросу st будет переделывать строку st в [c|с|С|s][t|т|Т] и будет искать WHERE 'regexpfield' LIKE '[c|с|С|s][t|т|Т]%' и под эту запись будут проходить и Cтан и СТ

А там где нужно находить полное соответствие (тоесть обработчику, который должен определять - нет ли уже записи ст в таблице)
придётся работать с регулярками полного совпадения ^[c|с|С|s][t|т|Т]$


-----
Truly yours, Sasha.
 
My status
 Top
EuGen Администратор
Отправлено: 28 Июня, 2007 - 09:42:19
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




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


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok
Отправлено: 28 Июня, 2007 - 09:50:51
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)




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


-----
Truly yours, Sasha.
 
My status
 Top
EuGen Администратор
Отправлено: 28 Июня, 2007 - 09:57:18
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Хорошо, быть может, у Вас и получится решить эту задачу и Вы сможете мне помочь, я бы очень хотел, чтобы получилось!


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok
Отправлено: 28 Июня, 2007 - 10:02:14
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)




тогда придётся пере описать как то задачу =)


-----
Truly yours, Sasha.
 
My status
 Top
EuGen Администратор
Отправлено: 28 Июня, 2007 - 10:17:17
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Что же, пробую еще раз, менее отвлекаясь уже на описание среды где это используется (потому что в первом описании, по моему, о ней уже все сказано)
Итак, предположим у нас в таблице базы (обзову ее тогда "T") есть записи с некоторыми регулярным выражениями (обзовем поле, в котором хранятся наши регулярки, как T.REG)
Пользователь желает узнать, можно ли в базу добавлять строку S0. Для этого он делает запрос к скрипту-поисковику. Тот, в свою очередь, делает запрос
SELECT * FROM T WHERE S0 REGEXP T.REG
И по логике получает, что, если S0 не подпадает ни под одно имеющееся в T.REG выражение, то S0 можно добавить в T, где S0 уже будет считаться регулярным выражением.
Далее, скрипт обработчик должен по входной строке S1 найти единственную запись в T, которой соответствует S1. Делает он это так:
SELECT * FROM T WHERE S1 REGEXP T.REG
Соответственно, он находит запись в T, поле T.REG которой есть регулярное выражение, под которое подпадает S1.
А теперь представим себе такую ситуацию:
-на момент добавления S0 в T существовала запись, T.REG которой соответствует некоторой строке S2, причем S0 есть подстрока S2.
-Обработчик начнет искать в T указанным запросом строку S2. Тогда, так как S2 REGEXP (T.REG, соответствующее S2) есть истина, и S2 REGEXP S0 есть истина, мы получим не 1, а 2 записи, то есть крах системы.
Собственно, задача состоит в том, чтобы такого не допустить и как то обрабатывать описанные ситуации, причем делать это по логике надо еще на стадии поисковика, то есть не давать юзеру вводить S0, если есть T.REG такое, что для него существует S2 и S0 есть подстрока S2.
Вообще говоря, мне кажется, что случай с подстроками не единственный возможный случай коллизии.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Страниц (2): [1] 2 »
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0)
« Регулярные выражения »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB