Часть слова

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

Алгоритмы

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

Приложения

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

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

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

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

Ссылки

^ Бланше-Садри, Франсин (2008), Алгоритмическая комбинаторика частичных слов , Дискретная математика и ее приложения, Бока-Ратон, Флорида: Chapman & Hall/CRC, ISBN 978-1-4200-6092-8 , МР 2384993
^ Пинтер, Рон Ю. (1985), «Эффективное сопоставление строк с шаблонами безразличия», Комбинаторные алгоритмы над словами (Maratea, 1984) , NATO Adv. наук. Инст. Сер. Ф Вычисление. Системные науки, том. 12, Шпрингер, Берлин, стр. 11–29, MR 0815329.
^ Манбер, Уди ; Баеза-Йейтс, Рикардо (1991), «Алгоритм сопоставления строк с последовательностью безразличий», Information Processing Letters , 37 (3): 133–136, doi : 10.1016/0020-0190(91)90032- Д , МР 1095695
^ Калаи, Адам (2002), «Эффективное сопоставление с образцом без забот» , в Эппштейне, Дэвиде (редактор), Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, 6-8 января 2002 г., Сан-Франциско , Калифорния, США , ACM и SIAM, стр. 655–656.
^ Файги, Ю. ; Гольдвассер, С .; Ловас, Л. ; Сафра, С ; Сегеди, М. (1991), «Аппроксимирующая клика почти NP-полна», Proc. 32-й симпозиум IEEE. «Основы информатики» , стр. 2–12, doi : 10.1109/SFCS.1991.185341 , ISBN. 0-8186-2445-0 , S2CID 46605913
^ Карно, Морис (1953), «Метод карт для синтеза комбинационных логических схем», Труды Американского института инженеров-электриков, Часть I: Связь и электроника , 1953 (5): 593–599, doi : 10.1109/TCE. 1953,6371932 , МР 0069032 , S2CID 51636736
^ Премель, Ханс Юрген (2002), «Большие числа, обозначение стрелки Кнута и теория Рамсея», Synthese , 133 (1–2): 87–105, doi : 10.1023/A:1020879709125 , JSTOR 20117296 , MR 1950045 , S2CID 1833 0949

[1] Бланше-Садри, Франсин (2008), Алгоритмическая комбинаторика частичных слов , Дискретная математика и ее приложения, Бока-Ратон, Флорида: Chapman & Hall/CRC, ISBN 978-1-4200-6092-8 , МР 2384993

[2] Пинтер, Рон Ю. (1985), «Эффективное сопоставление строк с шаблонами безразличия», Комбинаторные алгоритмы над словами (Maratea, 1984) , NATO Adv. наук. Инст. Сер. Ф Вычисление. Системные науки, том. 12, Шпрингер, Берлин, стр. 11–29, MR 0815329.

[3] Манбер, Уди ; Баеза-Йейтс, Рикардо (1991), «Алгоритм сопоставления строк с последовательностью безразличий», Information Processing Letters , 37 (3): 133–136, doi : 10.1016/0020-0190(91)90032- Д , МР 1095695

[4] Калаи, Адам (2002), «Эффективное сопоставление с образцом без забот» , в Эппштейне, Дэвиде (редактор), Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, 6-8 января 2002 г., Сан-Франциско , Калифорния, США , ACM и SIAM, стр. 655–656.

[5] Файги, Ю. ; Гольдвассер, С .; Ловас, Л. ; Сафра, С ; Сегеди, М. (1991), «Аппроксимирующая клика почти NP-полна», Proc. 32-й симпозиум IEEE. «Основы информатики» , стр. 2–12, doi : 10.1109/SFCS.1991.185341 , ISBN. 0-8186-2445-0 , S2CID 46605913

[6] Карно, Морис (1953), «Метод карт для синтеза комбинационных логических схем», Труды Американского института инженеров-электриков, Часть I: Связь и электроника , 1953 (5): 593–599, doi : 10.1109/TCE. 1953,6371932 , МР 0069032 , S2CID 51636736

[7] Премель, Ханс Юрген (2002), «Большие числа, обозначение стрелки Кнута и теория Рамсея», Synthese , 133 (1–2): 87–105, doi : 10.1023/A:1020879709125 , JSTOR 20117296 , MR 1950045 , S2CID 1833 0949

[1]

[2]

[3]

[4]

[5]

[6]

[7]