Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Sequitur (немесе Невилл Маннинг–Виттен алгоритмі) — 1997 жылы Крейг Невилл Маннинг пен Иан Х. Виттен жасаған, дискретті символдар тізбегінен иерархиялық құрылымды (контекстсіз грамматиканы) анықтайтын рекурсивті алгоритм. Алгоритм сызықтық кеңістікте және уақытта жұмыс істейді. Оны деректерді қысу бағдарламаларында пайдалануға болады.
Sequitur (or Nevill Manning–Witten algorithm) is a recursive algorithm developed by Craig Nevill Manning and Ian H. Witten in 1997 that infers a hierarchical structure (context free grammar) from a sequence of discrete symbols. The algorithm operates in linear space and time. It can be used in data compression software applications.
Диграмның бірегейлігі
Қатардан жаңа символ оқылған сайын, ол соңғы оқылған символмен біріктіріліп, жаңа диграмма құрайды. Егер осы диграмма бұрын құрылған болса, онда диграммалардың екі рет кездесуін алмастыру үшін жаңа ереже жасалады. Осылайша, грамматикада бір диграмма екі реттен көп кездеспейтіні қамтамасыз етіледі. Мысалы, S→abaaba тізбегінде алғашқы төрт символ оқылғанда, ab, ba, aa диграммалары пайда болады. Бесінші символ оқылғанда, жаңа 'ab' диграммасы құрылады, ол бұрыннан бар. Сондықтан, 'ab' диграммасының екі кездесуі де S-те жаңа ережемен (мысалы, A) ауыстырылады. Енді грамматика S→AaAa, A→ab түріне өтеді, және грамматикада қайталанатын диграммалар қалғанша процесс жалғаса береді.
Whenever a new symbol is scanned from the sequence, it is appended with the last scanned symbol to form a new digram. If this digram has been formed earlier then a new rule is made to replace both occurrences of the digrams. Therefore, it ensures that no digram occurs more than once in the grammar. For example, in the sequence S→abaaba, when the first four symbols are already scanned, digrams formed are ab, ba, aa. When the fifth symbol is read, a new digram 'ab' is formed which exists already. Therefore, both instances of 'ab' are replaced by a new rule (say, A) in S. Now, the grammar becomes S→AaAa, A→ab, and the process continues until no repeated digram exists in the grammar.
Ереже пайдалылығы
Бұл шектеу грамматиканың барлық өнімдерінің оң жағындағы барлық ережелердің кемінде бір рет қолданылуын қамтамасыз етеді, яғни егер ереже тек бір рет кездессе, оны грамматикадан жою керек және оның орнына оны құраған символдар қойылуы тиіс. Мысалы, жоғарыдағы мысалда, егер соңғы символ сканерленіп, 'Aa' үшін диграммалық бірегейлік қолданылса, грамматика S→BB, A→ab, B→Aa түрінде болады. Ереже 'A' грамматикада B→Aa өнімінде бір рет ғана кездеседі. Сондықтан, 'A' ережесі жойылады және ақырында грамматика S→BB, B→aba түріне келеді. Бұл шектеу грамматикадағы ережелер санын азайтуға көмектеседі.
This constraint ensures that all the rules are used more than once in the right sides of all the productions of the grammar, i. e., if a rule occurs just once, it should be removed from the grammar and its occurrence should be substituted with the symbols from which it is created. For example, in the above example, if one scans the last symbol and applies digram uniqueness for 'Aa', then the grammar will produce: S→BB, A→ab, B→Aa. Now, rule 'A' occurs only once in the grammar in B→Aa. Therefore, A is deleted and finally the grammar becomes
S→BB, B→aba. This constraint helps reduce the number of rules in the grammar.
Әдістің қысқаша мазмұны
Алгоритм терминал символдар тізбесін сканерлеу арқылы жұмыс істейді және ол оқыған барлық символ жұптарының тізімін құрайды. Кез келген жұптың екінші рет кездесуі анықталғанда, тізбектегі екі оқиға да жаңадан ойлап табылған терминалды емес символмен алмастырылады, символ жұптарының тізімі жаңа тізбекке сәйкес жаңартылады және сканерлеу жалғасады. Егер жұптың терминалды емес символы тек қана құрылған символдың анықтамасында қолданылса, қолданылған символ оның анықтамасымен алмастырылады және бұл символ анықталған терминалды емес символдар тізімінен жойылады. Сканерлеу аяқталғаннан кейін, түрлендірілген тізбек бастапқы тізбек үшін грамматикадағы жоғарғы деңгейлі ереже ретінде қарастырылуы мүмкін. Бұл символдардағы терминалды емес символдар үшін ереже анықтамаларын символ жұптары тізімінен табуға болады. Бұл ереже анықтамалары өзінде қосымша терминалды емес символдарды қамтуы мүмкін, олардың ережелерін символ жұптары тізіміндегі басқа жерлерден де оқуға болады.
The algorithm works by scanning a sequence of terminal symbols and building a list of all the symbol pairs which it has read. Whenever a second occurrence of a pair is discovered, the two occurrences are replaced in the sequence by an invented nonterminal symbol, the list of symbol pairs is adjusted to match the new sequence, and scanning continues. If a pair's nonterminal symbol is used only in the just created symbol's definition, the used symbol is replaced by its definition and the symbol is removed from the defined nonterminal symbols. Once the scanning has been completed, the transformed sequence can be interpreted as the top level rule in a grammar for the original sequence. The rule definitions for the nonterminal symbols which it contains can be found in the list of symbol pairs. Those rule definitions may themselves contain additional nonterminal symbols whose rule definitions can also be read from elsewhere in the list of symbol pairs.