Лабораторная работа "Обработка текста"

Лабораторная  работа 10

Обработка текста. Часть 2.

Древовидный словарь

1. Создание базы данных

Представим словарь в виде двоичного  дерева типа Right-Down

domains 
mark = y;n. 
tree = node(tree Down,char,mark Mark,tree Right); empty.  
dict = d(unsigned Counter, tree Tree).

Словарь dict содержит счётчик слов Counter и дерево Tree. Само древо представляется термом node(tree Down,char,mark Mark,tree Right). Этот терм описывает дерево с корневой вершиной char и двумя поддеревьями Down и Right. Эти поддеревья имеют такую же структуру, как и дерево. Метка Mark = y определяет букву, завершающую слово, а при Mark = n все неконечные буквы слова.

Предикаты для работы со словарём:

class predicates

create_dict: (string Text) -> dict Dict procedure. % создание словарь 
 
add_dict: (string Text, dict Dict) -> dict Dict procedure. % добавление в словарь 
next_word: (string Text, string Remainder, char Letter, string Last) determ (i,o,o,o). 
insert_Chars: (char, tree, string) -> tree determ (i,i,i). 
insert_LastChar: (char, tree) -> tree determ (i,i). 
 
get_item_nd: (dict,string) nondeterm (i,o).   % получение слова из словаря 
get_itemA_nd: (tree,string,string) nondeterm (i,i,o). 
 
search_token: (dict, string Token) nondeterm (i,i). % поиск заданного слова в словаре 
search_token1: (tree, char, string) nondeterm (i,i,i). 
 
insert_letter: (dict, string Token, string Correct) nondeterm (i,i,o). % восстановление слова с потерянной буквой 
insert_letter1: (tree,char,string, string,string,mark) nondeterm (i,i,i,i,o,i). 
get_LastLetter: (tree,char EndofWord) nondeterm (i,o). 
 
without_letter: (dict, string Token, string Correct) nondeterm (i,i,o). % восстановление слова с лишней буквой 
 
substitution_letter: (dict, string Token, string Correct) nondeterm (i,i,o). % восстановление слова с неправильной буквой 
substitution_letter1: (tree,char,string, string,string,mark) nondeterm (i,i,i,i,o,i). 
 
change: (dict, string Token, string Correct) nondeterm (i,i,o). % восстановление слова обменом соседних букв

Пример 1. Консольное приложение, реализующее словарь представлено ниже.

implement main 
open core,console,string 
 
constants 
className = "main". 
classVersion = "". 
 
domains 
mark = y;n. 
tree = node(tree Down,char,mark Mark,tree Right); empty. % Down-right tree of dictionary 
dict = d(unsigned Counter, tree Tree). 
 
class predicates 
create_dict: (string Text) -> dict Dict procedure. 
add_dict: (string Text, dict Dict) -> dict Dict procedure. 
next_word: (string Text, string Remainder, char Letter, string Last) determ (i,o,o,o). 
insert_Chars: (char, tree, string) -> tree determ (i,i,i). 
insert_LastChar: (char, tree) -> tree determ (i,i). 
get_item_nd: (dict,string) nondeterm (i,o). 
get_itemA_nd: (tree,string,string) nondeterm (i,i,o). 
try_search_token: (dict, string Token) nondeterm (i,i). 
search_token: (tree, char, string) nondeterm (i,i,i). 
insert_letter: (dict, string Token, string Correct) nondeterm (i,i,o). 
insert_letter1: (tree,char,string, string,string,mark) nondeterm (i,i,i,i,o,i). 
get_LastLetter: (tree,char EndofWord) nondeterm (i,o). 
 
clauses 
classInfo(className, classVersion). 
 
create_dict(Text) = add_dict(toLowerCase(Text), d(0,empty)). 
 
add_dict(Text, d(C,Tree)) = add_dict(Text1, d(C+1,Tree1)) :-  
        next_word(toLowerCase(Text),Text1,Char,Chars), Tree1 = insert_Chars(Char,Tree,Chars),!. 
add_dict(_,Dict) = Dict. 
 
next_word(Text,Text0,Char0,Chars0) :- fronttoken(Text,Token,Text1),frontchar(Token,Char1,Chars1), 
        if hasAlpha(Token) then Text0=Text1, Char0=Char1, Chars0=Chars1 else next_word(Text1,Text0,Char0,Chars0) end if,!. 
 
insert_Chars(Char,empty,Chars) = node(insert_Chars(Char1,empty,Chars1),Char,n,empty) :- 
        frontchar(Chars,Char1,Chars1),!. 
insert_Chars(Char,node(Down,Char,Mark,Right),Chars) = node(insert_Chars(Char1,Down,Chars1),Char,Mark,Right) :- 
        frontchar(Chars,Char1,Chars1),!. 
insert_Chars(Char,node(Down,Char0,Mark,Right),Chars) = node(Down,Char0,Mark,insert_Chars(Char,Right,Chars)) :- 
        Char>Char0,!.  
insert_Chars(Char,node(Down,Char0,Mark,Right),Chars) = node(insert_Chars(Char1,empty,Chars1),Char,n,node(Down,Char0,Mark,Right)) :- 
        Char<Char0, frontchar(Chars,Char1,Chars1),!.  
insert_Chars(Char,Tree,"") = insert_LastChar(Char,Tree). 
 
insert_LastChar(Char,empty) = node(empty,Char,y,empty) :- !. 
insert_LastChar(Char,node(Down,Char,_,Right)) = node(Down,Char,y,Right) :- !. 
insert_LastChar(Char,node(Down,Char1,Mark,Right)) = node(empty,Char,y,node(Down,Char1,Mark,Right)) :- Char<Char1. 
 
get_item_nd(d(_,Tree), Token) :- get_itemA_nd(Tree, "", Token). 
 
get_itemA_nd(node(_,Char,y,_),Chars,concat(Chars,charToString(Char))). 
get_itemA_nd(node(Down,Char,_,_),Chars,Token) :- get_itemA_nd(Down,concat(Chars,charToString(Char)),Token). 
get_itemA_nd(node(_,_,_,Right),Chars,Token) :- get_itemA_nd(Right,Chars,Token). 
 
try_search_token(d(_,Tree), Token):- frontchar(toLowerCase(Token),Char,Token1), search_token(Tree,Char,Token1). 
 
search_token(node(_,Char,y,_),Char,"") :- !. 
search_token(node(Down,Char,_,_),Char,Token) :- frontchar(Token,Char1,Token1),!,search_token(Down,Char1,Token1). 
search_token(node(_,Char1,_,Right),Char,Token) :- Char>Char1,search_token(Right,Char,Token). 
 
insert_letter(d(_,Tree), Token, Correct):- frontchar(toLowerCase(Token),Char,Token1), insert_letter1(Tree,Char,Token1,"",Correct,n). 
 
insert_letter1(node(_,Char,y,_),Char,"",Accum,concat(Accum,charToString(Char)),y). 
insert_letter1(node(Down,Char,_,_),Char,Token,Accum,Correct,SL) :- frontchar(Token,Char1,Token1), 
        insert_letter1(Down,Char1,Token1,concat(Accum,charToString(Char)),Correct,SL). 
insert_letter1(node(_,Char1,_,Right),Char,Token,Accum,Correct,SL) :- Char>Char1,insert_letter1(Right,Char,Token,Accum,Correct,SL). 
 
insert_letter1(node(Down,Char,n,_),Char,"",Accum,concat(Accum,charToString(Char),charToString(Letter)),n) :- get_LastLetter(Down,Letter). 
insert_letter1(node(Down,Char1,_,_),Char,Token,Accum,Correct,n) :- insert_letter1(Down,Char,Token,concat(Accum,charToString(Char1)),Correct,y). 
 
get_LastLetter(node(_,Char,y,_),Char). 
get_LastLetter(node(_,_,_,Right),Char) :- get_LastLetter(Right,Char). 
 
run():-init(), 
        D0=create_dict("Мартышка бросила кирпич - хватил удава паралич!"), 
        D=add_dict("Идёт мартышка вдоль пруда, идёт туда, потом сюда.",D0), 
        D=d(N,T), 
        I=length(tostring(T)), 
        write("Кол-во слов: ",N,"\nРазмер древа в байтах: ",I,"\nДерево: ",T,"\n"), 
        foreach get_item_nd(D,Token) do write(Token),nl  end foreach, 
        if try_search_token(D,"вдоль"),! then write("есть слово"),nl else write("нет слова"),nl end if, 
        write([IL||insert_letter(D,"мртышка",IL)]),nl, 
        _=readline(). 
         
end implement main 
 
goal 
    mainExe::run(main::run).

Скопируйте этот проект в консольное приложение и исследуйте его работу.

Задача 1. Исследуйте рост размера словаря, обучая его на больших текстах.

Задача 2. Разработайте GUI-приложение, позволяющее создавать словари и сохранять их в файлах БД.

Задача 3. Усовершенствуйте программу так, чтобы она позволяла заменять неправильно написанные слова (у которых есть пропуск буквы).

Задача 4. Усовершенствуйте поиск неправильных слов на основе удаления лишних букв и обмена местами смежных букв.