Skip to main content

Posts

Showing posts from February, 2018

Текстээс хайх Aho-Corasick алгоритм

Alfred V. Aho болон Margaret J. Corasick нарын эрдэмтэд 1975 онд зохиосон. Текстэн өгөгдлөөс олон дэд текстийг нэгэн зэрэг буюу параллель хайж олоход зорилго нь оршдог. Бичих, уншихад хялбар болгох үүднээс текстэн өгөгдлөө текст , хайж олох текстүүдээ үг  гээд нэрлэчихье (Англиар харгалзан  text , dictionary эсвэл text string , pattern string гэж нэрлэдэг). Үг бүрээр давтаж, давталтын алхам бүрд текстийг эхнээс нь дуустал нь давтах байдлаар бол хэн ч олчихно л доо. Харамсалтай нь маш өндөр өртөгтэй, текст уртсаж, үг олшрох тусам тэсвэрлэхийн аргагүй удаан ажиллах учраас тэгж программ бичиж, хүнд хэрэглүүлнэ гэж бол ёстой гонж. Бодит амьдралд ийм төрлийн ямар жишээнүүд байдаг вэ? Текстэн дэх товчилсон үг болон нэр томьёо бүрд тайлбар оруулах Утасны жагсаалт өгөгдсөн бол эздийг нь харгалзуулах Гений дарааллаас тодорхой бүтэцтэй генүүдийг илрүүлэх г.м бичээд байвал дуусашгүй их юм бий. Тэгээд яг яаж вэ?     Гол санаа нь ижил эхлэлтэй үгнүүдийн...