Создание регулярного выражения для списка строк

Question

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

Я хотел бы иметь возможность автоматически генерировать регулярные выражения для каждого столбца. Очевидно, что существуют нетривиальные решения, такие как .*, поэтому я бы добавить ограничения, которые они используют только:

• [A-Z] [a-z] [0-9]
• явные знаки препинания (например, ',', ''')
• "простые" кванторы (например {3,4}

«Лучший» ответ для таблицы выше:

[A-Z]{3} 
[A-Za-z\s\.]+ 
\d{4}\sm 
\d{2}\u00b0\d{2}'\d{2}"N,\d{2}\u00b0\d{2}'\d{2}"E 
(speciosissima|intermediate|troglodytes) 
(hf|sr) 
\d{4} 

Конечно, 4-е регулярное выражение сломается, если мы выйдем за пределы географической области, но программное обеспечение этого не знает. Целью было бы собрать много регулярных выражений, например, «Координаты» и обобщить их, возможно, частично вручную. Перечисления будут созданы только в том случае, если имеется небольшое количество отдельных строк.

Я был бы признателен за примеры программного обеспечения (особенно F/OSS), которые могут это сделать, особенно в Java. (Это похоже на Google Refine). Я знаю this question 4 years ago, но это действительно не отвечало на вопрос и на сайте text2re, который кажется интерактивным.

ПРИМЕЧАНИЕ. Я отмечаю, что голосование закрывается как «слишком локализованное». Это очень общая проблема (приведенная таблица - только пример), как показано в Google/Freebase, разрабатывающем Refine для решения проблемы. Это потенциально относится к очень широкому кругу таблиц (например, финансовой, журналистской и т. Д.). Вот один из значений с плавающей запятой:

Было бы полезно автоматически определить, что некоторые органы сообщают о возрасте в реальных количествах (например, не месяцах, днях) и используют 2 цифры точности.

Answer 1

Ваша особая проблема - частный случай «программирования демонстрацией». То есть, учитывая кучу примеров ввода/вывода, вы хотите сгенерировать программу. Для вас входные данные представляют собой строки, а выход - каждая строка принадлежит данному столбцу. В конце вы хотите создать программу на языке ограниченного регулярного выражения, которое вы предложили.

Этот конкретный пример программирования на демонстрации, по-видимому, тесно связан с Flash Fill, недавним проектом из MSR. Там вместо генерации регулярных выражений до соответствуют данных, они автоматически сгенерировали программы до transform строковые данные на основе примеров ввода/вывода.

Я только просматривал one своих документов, но я попытаюсь выложить то, что я понимаю здесь.

В этой статье представлены две основные идеи. Первым был дизайн небольшого языка программирования для представления строковых преобразований. Даже при использовании полноразмерных регулярных выражений создается слишком много возможностей для быстрого поиска. Они разработали свой собственный абстрактный язык для манипулирования строками; однако ваши ограничения (например, только с использованием простых кванторов), вероятно, будут играть ту же роль, что и их пользовательский язык.Это во многом возможно, потому что ваша конкретная проблема имеет несколько меньший объем, чем их.

Второе представление о том, как найти программы на этом абстрактном языке, которые соответствуют заданным парам ввода/вывода. Я понимаю, что ключевая идея здесь заключается в использовании техники под названием version space algebra. Грубое представление о пространственной алгебре версии состоит в том, что вы сохраняете представление о пространстве возможных программ и многократно обрезаете его, вводя дополнительные ограничения. Точные детали этого процесса хорошо укладываются в мои основные интересы, поэтому вам лучше читать что-то вроде этого introduction to version space algebra, в котором также содержится пример кода.

У них также есть некоторые умные подходы к ранжированию различных программ-кандидатов и даже догадываться, какие входы могут быть проблематичными для уже созданной программы. Я видел демоверсию, в которой они генерировали программу, не давая ей достаточного количества пар ввода/вывода, и программа могла бы действительно выделять новые входы, которые, вероятно, были бы неправильными. Такой вид рейтинга очень интересен, но требует более сложных методов машинного обучения и, вероятно, не сразу применим к вашему варианту использования. Тем не менее, может быть интересно. (Кроме того, это могло быть подробно описано в другой статье, чем в той, которую я связал.)

Итак, да, коротко говоря, вы можете генерировать свои выражения, подавая примеры ввода/вывода в систему на основе алгебры пространств версий. Надеюсь, это поможет.

Answer 2

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

1. расплющить [A-Z] к 'A'
2. расплющить [a-z] к 'a'
3. расплющить [0-9] к '0'
4. сглаживаются любые другие наборы специальный элемент кода (например, греческие символы) для одного символа (например, альфа)

Затем столбцы становятся:

1. "AAA"
2. "Aaaaaaaaaa", "Aaaaaaaaaaaaa", "Aaa aaa Aaaaaa" и т.д.
3. "0000 a"
4. "00\u00b000'00"N,00\u00b000'00"E
5. ...
6. ...
7. "0000"

я затем заменить их регулярными выражениями ч, как

1. "([A-Z])([A-Z])([A-Z])"
2. ...
3. "(\d)(\d)(\d)(\d)\s([0-9])"

и захватить отдельные символы в наборы. Это покажет, что (скажем) в 3.последний символ всегда "m", поэтому \d\d\d\d\s[m] и для 7. значение [2][0][0][458].

Для столбцов, которые не соответствуют этой модели, мы используем "(.*)" и видим, можем ли мы создавать полезные наборы (cols 5. и 6.) с эвристикой, такой как «как минимум 2 многократные строки и не более 50 % уникальных строк ".

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

Answer 3

В настоящее время я изучаю то же (или что-то подобное) (here). В общем случае это называется Grammar induction, или в случае регулярных выражений это induction of regular languages. В этом поле есть StaMinA competition. Общими алгоритмами являются RPNI и Blue-Fringe.

Here - другой родственный вопрос. И here другой. И here другой.