Неполное слово - Partial word

В Информатика и изучение комбинаторика слов, а частичное слово это нить который может содержать ряд символов «не знаю» или «не волнует», то есть заполнители в строке, где значение символа неизвестно или не указано. Более формально частичное слово - это частичная функция ${ displaystyle u: {0, ldots, n-1 } rightarrow A}$ куда ${ displaystyle A}$ - некоторый конечный алфавит. Если ты(k) не определено для некоторых ${ Displaystyle к ин {0, ldots, п-1 }}$ затем неизвестный элемент на месте k в струне называется «дырой». В обычные выражения (после POSIX стандарт) дыра представлена метасимвол ".". Например, aab.ab.b является частичным словом длины 8 по алфавиту А ={а,б}, в котором четвертый и седьмой символы являются дырами.^[1]

Алгоритмы

Было разработано несколько алгоритмов для задачи «сопоставление строк с безразличием», в которой входными данными являются длинный текст и более короткое частичное слово, а цель состоит в том, чтобы найти все строки в тексте, которые соответствуют заданному частичному слову.^[2][3][4]

Приложения

График совместимости частичных слов

Два неполных слова называются совместимый когда они имеют одинаковую длину и когда каждая позиция, которая не является подстановочным знаком в обоих из них, имеет одинаковый символ в обоих. Если сформировать неориентированный граф с вершиной для каждого частичного слова в наборе частичных слов и ребром для каждой совместимой пары, то клики этого графа происходят из наборов частичных слов, которые все соответствуют хотя бы одной общей строке. Эта теоретико-графическая интерпретация совместимости частичных слов играет ключевую роль в доказательстве твердость приближения из проблема клики, в котором набор частичных слов, представляющих успешное выполнение вероятностно проверяемое доказательство верификатор имеет большую клику тогда и только тогда, когда существует действительное доказательство базового НП-полный проблема.^[5]

Грани (подкубы) ${ displaystyle n}$-размерный гиперкуб можно описать частичными словами длины ${ displaystyle n}$ над двоичным алфавитом, эти символы являются Декартовы координаты вершин гиперкуба (например, 0 или 1 для единичный куб ). Размер вложенного куба в этом представлении равен количеству содержащихся в нем символов безразличия. Такое же представление может также использоваться для описания импликанты из Логические функции.^[6]

Связанные понятия

Частичные слова могут быть обобщены на слова параметров, в котором некоторые символы «не знаю» помечены как равные друг другу. Частичное слово - это частный случай параметрического слова, в котором каждый неизвестный символ может быть заменен символом независимо от всех остальных.^[7]

Рекомендации