Разрешение неоднозначных категорий в упорядоченном списке

Question

Давайте возьмем конкретный пример и надеемся, что я могу быть ясным. Предположим, (заказанный) список месяцев:

январь <февраль <март <... < Декабрь </p>

(с целыми числами, которые обозначают месяцы, начиная с нуля), так что

Январь 0, февраль 1, ..., декабрь 11.

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

е, F, е, е, е

Если я создам список «однозначных месяцев» (f: 1, s: 8, o: 9, n: 10, d: 11), я могу заполнить пустые категории, сначала вычислив первую категорию (используя вычитание и мод 12), а затем написать остальное оттуда. Однако предположим, что мне дали список

е, А, е, е, J, е

Тогда я могу (интуитивно) подсчитать, что хотя A является неоднозначным (может быть апрель или август), в этом контексте это может быть только апрель, поскольку в августе нет J после 2 категории. Как только я найду это, я снова смогу рассчитать все с самого начала.

Мой вопрос, наконец, таков: есть ли аналитическое решение (функция, алгоритм) для этой проблемы, или моя единственная надежда - использовать грубую силу для определения каждого потенциального отношения? В некоторых примерах алгоритм / функция устранения неоднозначности не может работать: рассмотрим случай, когда у меня есть J , затем 11 e , за которыми следует J к 11 e ... Так как между ними год, я не могу однозначно определить J в январе, июне или июле.

Ответ : Я закончил тем, что закодировал ответ Иль-Бхимы, потому что для этого случая, в частности, регулярные выражения в порядке, даже при большем времени выполнения O (mn). Тем не менее, я принял ответ Бена как правильный ответ, потому что он включает в себя другие (упоминает решение регулярных выражений), но также предлагает лучший способ с помощью алгоритма KMP O (m + n), хотя это для больших чисел строки против чтобы соответствовать шаблону. Спасибо всем.

Answer 1

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

Модификация будет сопоставлять что-либо с пустой категорией. Он может даже найти все возможные значения для вас, такие как J с 11 e, как вы упомянули.

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

Answer 2

Самый простой способ сделать это - использовать регулярные выражения. Предположим, вы хотите соответствовать e, A, e, e, J, e.

Создайте следующее регулярное выражение: r = ".A..J."

Пусть c будет нашей управляющей строкой:

  c = "JFMAMJJASONDJFMAMJJASOND"

Теперь мы ищем все совпадения r в строке c, где начальный индекс совпадения находится в первой половине c.

В общем, это может быть не самый эффективный метод. Наиболее наивное решение - попытка сопоставить шаблон с каждым циклическим сдвигом строки управления "JFMAMJJASOND" выполняется за O(nm) время, где n - длина шаблона, m - длина строки управления в нашем случае JFMAMJJASOND).

Answer 3

Мы можем основываться на ответе Иль-Бхимы немного для общего случая. Во-первых, мы признаем, что единственные действительно неоднозначные пары A, M или J - это два J, которые разделены на шесть месяцев, или две одинаковые буквы, которые на расстоянии один год. Любая другая комбинация приведет к однозначному совпадению в строке управления. (Я построил таблицу всех возможных комбинаций, чтобы доказать это.)

Таким образом, все, что вам нужно из всего вашего стартового списка, - это два месяца, в которых мод 12 расстояния не равен 0 или 6. Затем вы можете создать небольшое регулярное выражение для сопоставления со строкой управления. В качестве альтернативы вы можете создать справочную таблицу, содержащую упорядоченную пару и расстояния между месяцами.