Вот совершенно недавно столкнулся с задачкой, по которой не смог накопать не то, чтобы каких либо библиотек, но даже теории или алгоритмов. Т.к. время поджимало, решил сам разбираться с задачей. Написал статью для тех, кто с подобной задачей столкнется в будущем, да и интресна критика. Как бы вы решали подобную задачу?
На входе алгоритма есть набор строк S1..SN. Требуется, по данным строкам построить такое минимальное регулярное выражение R, чтобы R(Si)=true, i [1,N] (N порядка нескольких тысяч).
Требование минимальности — не строгое, и доказывать минимальность построенного regexp'a не требуется. Если строки S1..SN обладают некоторой схожей структурой, то regexp должен выявлять эту структуру. Стандартное задание программисту — в меру конкретизировано, но и с некоторой свободой действий.
UPD Пример…
Возьмем в качестве примера ссылки на некоторые статьи хабра:
Пример выполнен на Java. Тестировал на 6000 строках — построил мне регексп за 2 сек.
UPD Алгоритм реализован и работает. Строит достаточно конкретизированные регулярные выражения на приличных объемах данных за приемлимое время. Критикуйте и пользуйтесь.
UPD Поясню зачем это может понадовиться и почему простое объединение ^(S1|..|SN)$ не катит. Представте, что система работает с потоком строк F1,F2,F3,… Все строки схожей структуры (допустим урлы). Одни строки — «хорошие», другие — «не хорошие» :) А проверка на «хорошесть» — это очень затратная операция. Так вот, из общего потока строк после долгих проверок было выяснено, что строки S1..SN — это «хорошие» строки. В системе справедливо предположение, что если строка Fi будет иметь схожую структуру со строками S1..SN, то с большой степенью вероятности она будет «хорошей». Вот для этого и строится regexp на основании N строк — чтоб потом только по виду строки определять ее «хорошесть» :) Надеюсь не перемудрил с описанием :)
Итак, задача ...
На входе алгоритма есть набор строк S1..SN. Требуется, по данным строкам построить такое минимальное регулярное выражение R, чтобы R(Si)=true, i [1,N] (N порядка нескольких тысяч).
Требование минимальности — не строгое, и доказывать минимальность построенного regexp'a не требуется. Если строки S1..SN обладают некоторой схожей структурой, то regexp должен выявлять эту структуру. Стандартное задание программисту — в меру конкретизировано, но и с некоторой свободой действий.
Алгоритм решения ...
- Находим наименьшее регулярное выражение для строк S1 и S2:
- Дописываем каждой строке символы начала и конца строки, получается S1= ^S1$
- Ищем максимальную общую подстроку для S1 и S2. Пусть это U — это максимальная общая подстрока для S1,S2. (Есть несколько известных алгоритмов поиска максимальной общей подстроки, а если Вы располагаете средствами, то можете купить алгоритм Teiresias от IBM)
- Т.о. получается, что подстрока U делит каждую из строк S1 и S2 на 2 части — левую и правую:
S1: S1L || U || S1R
S2: S2L || U || S2R
где SiL и SiR -левые и правые подстроки строк S1 и S2.
- Как видно напрашивается рекурсия с бинарным деревом. Строку U ставим в корень дерева. Если обе строки S1L и S2L непусты, то создаем левый потомок и запускаем сравнение для них. Аналогично для правых подстрок.
U
/ \
UL UR
- Если на каким-то этапе общие подстроки не найдено (или она короткая, 1-2 символа), то ставим в текущий узел ".*" и выходим из последнего рекурсивного вызова. Это очень грубое выражение, но оно подхоит для моей задачи. На этом шаге большой простор для опримизации алгоритма под ваши нужды.
- После того как дерево построено, симметричным обходом его получаем искомое регулярное выражение SX для S1 и S2 (Возможно, придется еще раз добавить символы начала и конца выражения, т.к. в некоторых случаях они превращаются в ".*")
- Сравнивая полученную строку SX с S3 по тому же алгоритму получаем SX — регулярное выражение для первых 3-х строк.
- Индукцией по всем строкам получаем R=SX искомое регулярное выражение.
UPD Пример…
Возьмем в качестве примера ссылки на некоторые статьи хабра:
S1=http://habrahabr.ru/blogs/edu_2_0/40236/ true
S2=http://habrahabr.ru/blogs/microsites/40089/ true
S3=http://habrahabr.ru/blogs/google_chrome/38748/ true
S4=http://habrahabr.ru/blogs/show/37839/ true
S5=http://nikolaikopernik.habrahabr.ru/blog/54889/ true
S6=http://habrahabr.ru/blogs/telecom/39902/ true
-----------------
REGEXP = ^http://.*habrahabr.ru/blog.*/$
SIZE : 6
TIME : 0.0070 sПример выполнен на Java. Тестировал на 6000 строках — построил мне регексп за 2 сек.
UPD Алгоритм реализован и работает. Строит достаточно конкретизированные регулярные выражения на приличных объемах данных за приемлимое время. Критикуйте и пользуйтесь.
UPD Поясню зачем это может понадовиться и почему простое объединение ^(S1|..|SN)$ не катит. Представте, что система работает с потоком строк F1,F2,F3,… Все строки схожей структуры (допустим урлы). Одни строки — «хорошие», другие — «не хорошие» :) А проверка на «хорошесть» — это очень затратная операция. Так вот, из общего потока строк после долгих проверок было выяснено, что строки S1..SN — это «хорошие» строки. В системе справедливо предположение, что если строка Fi будет иметь схожую структуру со строками S1..SN, то с большой степенью вероятности она будет «хорошей». Вот для этого и строится regexp на основании N строк — чтоб потом только по виду строки определять ее «хорошесть» :) Надеюсь не перемудрил с описанием :)