Жолдарды сәйкестендірудің екі жақты алгоритмі - Two-way string-matching algorithm - Wikipedia

Сынып	Жолдарды іздеу алгоритмі
Мәліметтер құрылымы	Кез келген жіп тапсырыс берілген алфавитпен
Ең нашар өнімділік	O (n)
Ең жақсы жағдай өнімділік	O (n)
Ең нашар ғарыштық күрделілік	O (1)

Жылы Информатика, жолдарды сәйкестендірудің екі жақты алгоритмі тиімді болып табылады жол іздеу алгоритмі бұл болашақтың тіркесімі ретінде қарастырылуы мүмкін Кнут-Моррис-Пратт алгоритмі және артқа жүгіру Бойер – Мур жол іздеу алгоритмі. Максим Крохемор мен Доминик Перрин бұл алгоритмді 1991 жылы ойлап тапқан.^[1] Алдын ала өңдеу уақыты иненің өлшеміне сәйкес келеді. Ол 2n performance м салыстыру кезінде сызықтық нашар көрсеткіштерге ие.^[2] Бреслауердің салыстыруы азырақ болатын екі жетілдіруі бар: біреуі тұрақты кеңістік және n + еден (1 + eps / 2 × (n-m)) салыстыру, екіншісі лог (m) кеңістік және n + еден ((n-m)) 2) салыстырулар.^[3]

KMP және BM сияқты, алгоритмдер кестеде ішінара қайталанатын кезеңдерге негізделген ауысымдарды қолданады. Алайда, ол инені екіге бөлу (критикалық факторизация) арқылы жүзеге асырады, сондықтан алдын-ала өңдеуден тек бір мәнді есте сақтау қажет.

Алгоритм кэшке ыңғайлы және кітапхана функцияларымен ауыстыруға ыңғайлы амалдардан тұратын нақты жағдайда жеткілікті тиімді болып саналады. Ол ретінде таңдалады glibc (және алынған newlib; str-екі жақты.h) және мусл memmem және strstr функциялар тобының алгоритмі.^[4]^[5]^[6] Алайда, жол іздеудің ең жетілдірілген алгоритмдеріндегідей, пішеннің де, иненің де шығынсыздық нүктесі болады, оған дейін аңғал квадраттық (memchr-memcmp) іске асыру тиімдірек болады.^[7] Glibc Breslauer алгоритмін екі формада да ұсынады.^[6]

Критикалық факторизация

Критикалық факторизацияны анықтамас бұрын:^[1]

Факторизация: жол екі жартыға бөлінгенде көбейтілген деп саналады. Айталық, жол $х$ екі бөлікке бөлінеді $(u, v)$ , содан кейін $(u, v)$ факторизациясы деп аталады $х$ 。
Кезең: кезең $б$ жіп үшін $х$ кез келген бүтін сан үшін болатын мән ретінде анықталады $0 < мен \leq | х | - б$ , $х [мен] = х [мен + б]$ . Басқа сөздермен айтқанда, » $б$ кезеңі болып табылады $х$ егер екі әріп болса $х$ қашықтықта $б$ әрқашан сәйкес келеді «. минималды кезеңі $х$ деп натурал санмен белгіленеді $p (x)$ .
A қайталау w жылы (u, v) - субстрині х осылай:
- $w$ –ның жұрнағы болып табылады $сен$ немесе керісінше;
- $w$ префиксі болып табылады $v$ немесе керісінше;
Басқа сөздермен айтқанда, $w$ кесудің екі жағында да, екі жағында да толып кетуі мүмкін. Әрбір факторизацияда тривиальды түрде кем дегенде бір қайталау бар, жол $vu$ .^[2]
A жергілікті кезең - қайталану ұзындығы $(u, v)$ . Ең кіші жергілікті кезең $(u, v)$ деп белгіленеді $r (u, v)$ . Кез-келген факторизация үшін $0 < r (u, v) \leq | х |$ .
A критикалық факторизация факторизация болып табылады $(u, v)$ туралы $х$ осындай $r (u, v) = p (x)$ . Ұзындығы бар ине үшін $м$ тапсырыс берілген алфавитте оны есептеуге болады $2 м$ салыстыру, лексикографиялық тұрғыдан ordered және order реттері үшін анықталған екі реттелген максималды жұрнақтардың үлкенін есептеу арқылы.^[6]

Алгоритм

Алгоритм инені алдын-ала өңдеу сатысы ретінде критикалық факторизациядан басталады. Бұл қадам периодтық оң жартысының индексін (бастапқы нүктесін) және осы созылу кезеңін шығарады. Мұндағы жұрнақты есептеу авторлардың тұжырымдамасына сәйкес келеді. Оны баламалы түрде қарапайым арқылы есептеуге болады Дюваль алгоритмі, бұл баяу, сонымен қатар сызықтық уақыт.^[8]

Инверсияға арналған стенография.функциясы cmp (a, b) егер а> б қайту 1    егер a = b қайту 0    егер a қайту -1функциясы maxsuf (n, rev) l ← len (n) p ← 1 қазіргі уақытта белгілі кезең.    k ← 1 кезеңдік тестілеу индексі, 0     j ← 0 maxsuf тестілеу индексі. максимумнан үлкен.    мен ← -1 maxsuf ұсынылған бастапқы индексі        уақыт j + k егер rev cmpv ← -cmpv салыстыруды төңкеріңіз        егер cmpv <0 Жұрнақ (j + k) кішірек. Мерзім - бұл барлық префикс.            j ← j + k k ← 1 p ← j - i басқаша болса cmpv = 0 Олар бірдей - біз жалғастыруымыз керек.            егер k = p Біз р-дің созылуын тексеріп біттік. қалпына келтіру k.                j ← j + p k ← 1 басқа                k ← k + 1 басқа            Суффикс үлкенірек. Осы жерден бастаңыз.            i ← j j ← j + 1 p ← 1 k ← 1 қайту [i, p]функциясы crit_fact (n) [idx1, per1] ← maxsuf (n, false) [idx2, per2] ← maxsuf (n, true) егер idx1> idx2 қайту [idx1, per1] басқа        қайту [idx2, per2]

Салыстыру алдымен оң жаққа, содан кейін сәйкес келсе, сол жаққа сәйкес келеді. Сызықтық уақытқа секіру кезеңді қолдану арқылы жүзеге асырылады.

функциясы сәйкестік (n, h) nl ← len (n) hl ← len (h) [l, p] ← crit_fact (n) P ← {} матчтардың жиынтығы.         Жұрнақты сәйкестендіріңіз.    Memcmp сияқты кітапхана функциясын пайдаланыңыз немесе өз цикліңізді жазыңыз.    егер h [0] ... h [l] = h [p] ... h [l + p] P ← {} pos ← 0 s ← 0 ІСТЕУ. Ең болмағанда скипті салыңыз.

Пайдаланылған әдебиеттер

^ ^а ^б Crochemore, Maxime; Перрин, Доминик (1991 ж. 1 шілде). «Екі жақты жолдарды сәйкестендіру» (PDF). ACM журналы. 38 (3): 650–674. дои:10.1145/116825.116845.
^ ^а ^б «Екі жақты алгоритм».
^ Бреслауэр, Дани (мамыр 1996). «Crochemore-Perrin жолдарды сәйкестендіру алгоритмінде салыстыруларды сақтау». Теориялық информатика. 158 (1–2): 177–192. дои:10.1016/0304-3975(95)00068-2.
^ «musl / src / string / memmem.c». Алынған 23 қараша 2019.
^ «newlib / libc / string / memmem.c». Алынған 23 қараша 2019.
^ ^а ^б ^c «glibc / string / str-two-way.h».
^ «Эрик Блейк - Re: PATCH] меммемнің жұмысын жақсарту». Newlib тарату тізімі.
^ Адамчик, Збигнев; Риттер, Войцех (мамыр 2013). «Жолдың максималды қосымшасын қарапайым есептеу туралы жазба». Дискретті алгоритмдер журналы. 20: 61–64. дои:10.1016 / j.jda.2013.03.002.

[CP91-1] а ^б Crochemore, Maxime; Перрин, Доминик (1991 ж. 1 шілде). «Екі жақты жолдарды сәйкестендіру» (PDF). ACM журналы. 38 (3): 650–674. дои:10.1145/116825.116845.

[igm-mlv-2] а ^б «Екі жақты алгоритм».

[3] Бреслауэр, Дани (мамыр 1996). «Crochemore-Perrin жолдарды сәйкестендіру алгоритмінде салыстыруларды сақтау». Теориялық информатика. 158 (1–2): 177–192. дои:10.1016/0304-3975(95)00068-2.

[4] «musl / src / string / memmem.c». Алынған 23 қараша 2019.

[5] «newlib / libc / string / memmem.c». Алынған 23 қараша 2019.

[str-two-way-6] а ^б ^c «glibc / string / str-two-way.h».

[7] «Эрик Блейк - Re: PATCH] меммемнің жұмысын жақсарту». Newlib тарату тізімі.

[8] Адамчик, Збигнев; Риттер, Войцех (мамыр 2013). «Жолдың максималды қосымшасын қарапайым есептеу туралы жазба». Дискретті алгоритмдер журналы. 20: 61–64. дои:10.1016 / j.jda.2013.03.002.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]