Подходы для реверсирования формата sprintf / - PullRequest
Новая
       8

Подходы для реверсирования формата sprintf /

6 голосов
/ 11 февраля 2011

Я должен эвристически определить строки шаблона формата, анализируя отформатированные результаты.

Например, у меня есть следующие строки:

У вас есть 3 непрочитаносообщения.

У вас есть 10 непрочитанных сообщений.

Извините, Дейв .Боюсь, я не могу этого сделать.

Извините, Фрэнк .Боюсь, я не могу этого сделать.

Это утверждение неверно.

Я хочу получить строки этого формата:

У вас есть% s непрочитанных сообщений

Извините, % s .Боюсь, я не могу этого сделать.

Это утверждение неверно.

Какие подходы и / или алгоритмы могут мне здесь помочь?

Моей первой мыслью было использование машинного обучения, но мои смелости говорят мне, что это может быть довольно классической проблемой.

Некоторые дополнительные требования:

  • Тип параметра не имеет значения, т.е. мне не нужна информация, если параметр изначально был %s или %d или если онбыл дополнен или выровнен.
  • Может быть более одного параметра (или его вообще нет)
  • Обычно данные состоят из тысяч отформатированных строк, но только из десятков шаблонов формата.

1 Ответ

1 голос
/ 11 февраля 2011

  1. Кластеризация строк по метрике сходства (я бы попробовал длину самой длинной общей подпоследовательности, LCS). Определение количества кластеров - сложная часть, если вы не знаете ее заранее.

  2. В каждом кластере определите LCS всех строк в нем,запись положения возникающих пробелов.Заменить пробелы на %s.(Вы можете захотеть создать функцию, которая возвращает строку формата на основе LCS и fold / reduce для кластера.)

Выше приведен жадный алгоритм, которыйданный {foobar, fooBaR} производит foo%sa%s.Возможно, вы захотите заменить любую пару вхождений %s, разделенных одним символом (или одним непробельным символом и т. Д.), На один %s, рекурсивно.

...