Самый быстрый способ подбора строки, используя подстановочный знак DOS - PullRequest
Новая
       23

Самый быстрый способ подбора строки, используя подстановочный знак DOS

6 голосов
/ 14 мая 2009

Эта проблема похожа на слепые инъекции SQL. Цель состоит в том, чтобы определить точное значение строки, и единственный тест, который вы можете сделать, состоит в том, чтобы проверить, соответствует ли указанная вами подстановочный знак в стиле DOS (? = Любой символ, * = любое количество любых символов), который вы указали. (Так что практически у вас есть доступ только к функции bool DoesWildcardMatch(string wildcard)).

Простой способ - проверить a*, b*, c*..., пока не найдете первую букву, а затем повторите. Некоторые оптимизации, которые я могу придумать:

  • поиск *a*, *b* и т. Д. Для определения набора символов
  • когда совпадение на *x* найдено, выполните функцию разделяй и властвуй (*a*x*, *b*x*, ...)

Ответы [ 4 ]

2 голосов
/ 14 мая 2009

Первая мысль. Вы можете определить длину n строки в O(log2(n)).

  • Проверка Z*, где Z представляет k вопросительные знаки, начиная с 0, затем 1, а затем удваивая количество вопросительных знаков при каждой проверке, пока не будет найдено совпадение. n должно быть между k / 2 и k
  • Найти точную длину, используя тот же шаблон, изменяющий k так же, как это делает бинарный поиск.

Знание точной длины может помочь выполнить своего рода «разделяй и властвуй» в пространственной области.

UPDATE

Если вы знаете длину, вы можете использовать тот же шаблон, чтобы правильно найти символ.

* +1025 * Пример: 
    ..X. ..XX (spaces added for readability)

                              + symbol may be X
                              - symbol is not X
                              X symbol is X

    *X*         => MATCH      ++++ ++++
    *X*   ????  => MATCH      ++++ ++++
    *X*?? ????  => NO MATCH   --++ ++++
    ??X?  ????  => MATCH      --X+ ++++
    ??XX  ????  => NO MATCH   --X- ++++
    ??X?  *X*?? => NO MATCH   --X- --++
    ??X?  ??X?  => MATCH      --X- --X+
    ??X?  ??XX  => MATCH      --X- --XX

Для длины строки n и размера алфавита m это займет около O(log2(n)), чтобы найти длину строки, около O(n • log2(n)), чтобы правильно разместить n символов, и O(m), чтобы найти используемые символы - суммируя все вместе, получаем O(n • log2(n) + m).

Я мог бы предположить, что это можно ускорить, объединив несколько шагов - возможно, проверьте используемые символы при определении длины строки или одновременно обнаружив два (или даже больше?) Символа в первой и второй половине строки. Это потребует повторной проверки объединенных шагов в случае неудачной проверки, чтобы определить, какая проверка не удалась. Но до тех пор, пока объединенная проверка завершится успешно, вы получите информацию об обоих.

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

2 голосов
/ 14 мая 2009

Что касается «разделяй и властвуй», то обязательно следите за тем значением, которого, как вам известно, нет. Также я бы не пошел с a, b, c, но с частотным порядком. Какая-то цепочка Маркова из этого может сделать это еще быстрее.

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

c a b a
--------
* a *     match
  * b*a*  woops!
1 голос
/ 14 мая 2009

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

Я думаю, что метод деления с проверкой набора символов перед почти оптимален, есть некоторые дополнительные детали, например, если вы выбрали *a*b*, вы должны проверить *ab* впоследствии, чтобы узнать, есть ли буквы между и Конечно, как указано выше, проверьте *ab и «ab» после этого, чтобы узнать, закончили ли вы с правой стороны или полностью.

0 голосов
/ 14 мая 2009

Почему бы не преобразовать вашу подстановочную строку в стиле DOS в регулярное выражение? e.g.:

? А *

становится:

.А. *

Затем просто выполните простое сопоставление с регулярным выражением, сравнивая его с вашей тестовой строкой.

...