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

Question

У меня потеря предложений, сгенерированных из http://www.ywing.net/graphicspaper.php, генератора случайных заголовков компьютерной графики, некоторые из примеров отсортированных предложений выглядят следующим образом:

---

• Аннотация Окружающая окклюзия с использованиемОтображение текстуры
• Абстрактное отображение текстуры окружающей среды
• Абстрактные анизотропные мягкие тени
• Абстрактное приближение
• Абстрактное приближение адаптивных мягких теней с использованием отбраковки
• Абстрактная аппроксимация внешней окклюзии с использованием аппаратно-ускоренной кластеризации
• Абстрактная аппроксимация распределенных поверхностей с использованием оценки
• Абстрактная аппроксимация геометрии для текстурированной картографической окклюзии окружающей среды
• Абстрактная аппроксимация Mipmaps дляНепрозрачность
• Абстрактное приближение полей окклюзии для подповерхностного рассеяния
• Абстрактное приближение мягких теней с использованием отражающего текстурирования
• Абстрактное произвольное отображение
• Абстрактное затухание и смещение Mприменение геометрии
• Абстрактное затухание внешней окклюзии с использованием зависимого от вида наложения текстуры
• Абстрактное затухание световых полей для мип-карт
• Абстрактное затухание нелинейной внешней окклюзии
• Аннотация Затухание предварительно вычисленных Mip-карт с использованием повторного построения

  - ...

Я хотел бы попробовать обратную инженерию грамматики и научиться делать это вкакие-то способы, как обычным способом LISP или NLTK.Есть идеи по этому поводу?

- Дрейк

Answer 1

Вас может заинтересовать Обучение на основе выравнивания Менно ван Заанена.Прошло много лет с тех пор, как я читал его статьи, но основная идея состоит в том, чтобы

1. найти общую подстроку
2. назначить ей правило грамматики
3. переписать текстиспользуйте это правило
4. проверьте, короче ли переписанный текст + грамматика, чем исходный текст.

Запустите это для всех комбинаций всех общих подстрок, чтобы найти лучшую грамматику.

Это немного похоже на то, что будет делать оптимальный алгоритм сжатия.Теория, стоящая за этим, Минимальная длина описания .

Answer 2

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

Также Википедия перечисляет некоторые другие подходы.

Answer 3

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

Простой способ - создать дерево разбора и создать словарь в каждой части дерева.

Примерно так:

  Abstract
  |--------|
           |Ambient , Anisotropic,(Approximation, Attenuation)
                                        |
                                        of
                                        |
                                   xxxx      yyyy
                                     |         |
                                   using       for

xxxx ->список словарей

гггг -> список словарей