%% A Prolog program that finds correction suggestions
%% for misspelled words.

%% Code from:

/* *************************************
@Article{Berg87,
  author = 	 "H. Berghel",
  title = 	 "A logical framework for the correction of spelling
		  errors in electronic documents",
  journal =	 "Information Processing and Management",
  year =	 1987,
  volume =	 23,
  number =	 5,
  pages =	 "477-494",
}
**************************************** */

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Omission error ==> insert one character

is_an_element_of_omission(X) :-
  add_character(X,Y),
  word(Y),
  format("Found word via insertion: ~s~n",[Y]).
  

%% upon backtracking: inserts a variable at any position in the list

add_character(X, [_|X] ).

add_character( [U|V], [U|W] ) :-
  add_character(V, W).

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Insertion error ==> delete one character

is_an_element_of_insertion(X) :-
  delete_character(X,Y),
  word(Y),
  format("Found word via deletion: ~s~n",[Y]).

%% upon backtracking: deletes any position in the list

delete_character([_|Y], Y ).

delete_character( [U|V], [U|W] ) :-
  delete_character(V, W).

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Substitution error ==> replace one character

is_an_element_of_substitution(X) :-
  replace_character(X,Y),
  word(Y),
  format("Found word via substitution: ~s~n",[Y]).

%% upon backtracking: replaces any position in the list with a variable

replace_character([_|Y], [_|Y] ).

replace_character( [U|V], [U|W] ) :-
  replace_character(V, W).

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Transposition error ==> exchange two neighboring positions

is_an_element_of_transposition(X) :-
  transposes_to(X,Y),
  word(Y),
  format("Found word via transposition: ~s~n",[Y]).

%% upon backtracking: transpose any neighboring letter pair

transposes_to([], [] ).

transposes_to( [U|V], [U|W] ) :-
  transposes_to(V, W).

transposes_to( [X,Y|Z], [Y,X|Z] ).

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  
%% Fullform-lexicon as basis for the comparison.

word("the").
word("then").
word("hate").
word("hue").
word("he").
word("ate").

word("ball").
word("bald").
word("balk").
word("bad").
word("bag").
word("bar").

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Example usage:

%% ?- get_similarity_set("hte").
%% Found word via insertion: hate
%% Found word via deletion: he
%% Found word via substitution: ate
%% Found word via substitution: hue
%% Found word via transposition: the

%% ?- get_similarity_set("bal").
%% Found word via insertion: ball
%% Found word via insertion: ball
%% Found word via insertion: bald
%% Found word via insertion: balk
%% Found word via substitution: bad
%% Found word via substitution: bag
%% Found word via substitution: bar

%% Note: for this call, the word "ball" is found twice
%%       once for the "l" before the given "l"
%%   and once for the "l" after  the given "l"


%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Check all possible error sources.
get_similarity_set(Word) :-
  is_an_element_of_omission(Word),
  fail.

get_similarity_set(Word) :-
  is_an_element_of_insertion(Word),
  fail.

get_similarity_set(Word) :-
  is_an_element_of_substitution(Word),
  fail.

get_similarity_set(Word) :-
  is_an_element_of_transposition(Word),
  fail.

get_similarity_set(_).
