
Ахо-Корасик алгоритм: Олон үгийг нэгэн зэрэг хайдаг ухаалаг технологи

Б.Мөнх-Эрдэнэ
Багш


Б.Мөнх-Эрдэнэ
Багш
Бид өдөр бүр Google-ээс мэдээлэл хайж, мессеж бичиж, цахим шуудан уншиж, төрөл бүрийн программ ашигладаг. Гэвч эдгээр систем асар их хэмжээний текст дундаас хэрэгтэй үг, өгүүлбэрийг хэрхэн хурдан олдог талаар бодож үзсэн үү?
Жишээлбэл, нэг сая мөр текст дундаас 1000 өөр үгийг хайх шаардлагатай боллоо гэж төсөөлье. Үг бүрийг тус тусад нь хайвал компьютер олон дахин ижил текстийг шалгах хэрэгтэй болно.
Харин Ахо-Корасик (Aho–Corasick) хэмээх алгоритм олон үгийг нэгэн зэрэг хайх боломжийг олгодог.
Энэхүү алгоритмыг 1975 онд Альфред Ахо (Alfred Aho), Маргарет Корасик (Margaret Corasick) нар танилцуулсан бөгөөд өнөөдөр ч текст боловсруулах технологийн чухал алгоритмуудын нэг хэвээр байна.
Ахо-Корасик бол текст дотроос олон түлхүүр үгийг нэг удаагийн шалгалтаар илрүүлэх зориулалттай мөр хайлтын алгоритм юм.
Жишээлбэл, бид дараах үгсийг хайхыг хүсэж байна:
he, she, his, hers
Харин шалгах текст нь:
ushers
Энгийн хайлтаар дөрвөн үгийг тус тусад нь шалгаж болно. Харин Ахо-Корасик алгоритм текстийг зүүнээс баруун тийш нэг удаа уншихдаа тохирох үгсийг олдог.

Энд нэг сонирхолтой зүйл бий. she гэдэг үгийн сүүлийн хоёр үсэг нь he гэсэн өөр нэг хайж буй үгтэй давхцаж байна. Ахо-Корасик ийм давхцлыг ч алдалгүй илрүүлдэг.
Алгоритмын үндсэн ажиллагаа гурван үе шаттай.

Нэгдүгээр алхам: Trie мод байгуулах
Хайх үгсийг үсэг бүрээр нь салаалсан мод хэлбэрээр хадгална. Ижил эхлэлтэй үгс нэг замыг хуваалцдаг тул давхардсан мэдээллийг багасгадаг.

Хоёрдугаар алхам: Failure link үүсгэх
Хайлт тухайн замаар үргэлжлэх боломжгүй үед аль төлөв рүү шилжихийг заадаг холбоосуудыг байгуулна. Ингэснээр текстийн өмнө уншсан тэмдэгтүүдийг дахин шалгах шаардлагагүй.

Гуравдугаар алхам: Текстийг шалгах
Текстийн тэмдэгт бүрийг дарааллаар уншиж, автоматын төлөвийг шинэчилнэ. Үг таарсан төлөвт хүрэхэд тухайн үгийг илрүүлж, шаардлагатай бол давхцаж буй бусад үгийг мөн бүртгэнэ.
Үр дүн:
she: 1-3
he: 2-3Энэ кодод add_word() нь хайх үгсийг нэмдэг, make_automaton() нь хайлтын автоматыг бэлддэг, харин iter() нь текст доторх тохирлуудыг олдог.
Ахо-Корасик алгоритмын хугацааны төвөгшлийг ихэвчлэн дараах байдлаар илэрхийлдэг.
O(n+m+z)
Энд:
n — шалгах текстийн урт
m — хайх бүх үгсийн нийт урт
z — олдсон тохирлуудын тоо
Энэ нь автоматыг байгуулах болон бүх тохирлыг гаргах нийт ажиллагааны түгээмэл үнэлгээ юм. Бодит хэрэгжүүлэлтэд цагаан толгойн хэмжээ, өгөгдлийн бүтэц зэргээс хамаарч нэмэлт зардал гарч болно.
Жишээлбэл, нэг сая тэмдэгттэй текст дотроос 1000 үг хайх үед үг бүрээр текстийг дахин шалгахын оронд нэг автомат ашиглан хайлт хийх боломжтой.
Кибер аюулгүй байдал
Сүлжээний урсгал, лог файл дотроос сэжигтэй текстэн хэв маяг болон мэдэгдэж буй халдлагын тэмдэгт мөрүүдийг хайхад ашиглаж болно.
Спам болон зохисгүй агуулга илрүүлэх
Олон түлхүүр үг, хориотой хэллэгийг нэгэн зэрэг илрүүлэх системийн бүрэлдэхүүн хэсэг болгон ашиглаж болно.
Ахо-Корасик алгоритм нь компьютерын шинжлэх ухаанд зөв өгөгдлийн бүтэц сонгох нь ямар чухал болохыг харуулдаг гайхалтай жишээ юм.
Текстийг дахин дахин шалгахын оронд өмнө нь боловсруулсан мэдээллээ ашиглан олон үгийг нэгэн зэрэг хайж чаддаг нь энэхүү алгоритмын гол давуу тал юм.
Программчлал гэдэг нь зөвхөн код бичих биш, харин асуудлыг илүү ухаалгаар шийдэх арга замыг олох урлаг юм.