Я нашел здесь интересную статью в блоге об использовании Tries для исправления орфографических ошибок, однако она была написана в более старой версии F #.
http://blog.lab49.com/archives/2841
Я исправил большую часть этого, за исключением того самого конца, где я поместил комментарий во всех заглавных буквах, где я думаю, что что-то идет не так. В основном в нескольких местах ожидается Set, и Map <>, и наоборот. Я часами смотрю на этот кусочек кода и не могу понять, где что-то не так.
open System
open System.Linq
///'k represents the base key type, and 'a represents the element type.
type trie<'k,'a when 'k : comparison> = TNode of ('a option * Map<'k,trie<'k,'a>>)
///'ks represents a type that stores a sequence of the key elements, and 'k represents the type of the key elements.
type iter_module<'ks,'k> =
{
eos : ('ks -> bool) //whether or not a key-sequence is at its end.
head : ('ks -> 'k) //gets the current key-value in a key sequence
tail : ('ks -> 'ks) // increments the key-sequence iterator.
}
let siterm : iter_module<string * int, char> =
{
eos = fun (s,i) -> i >= String.length s
head = fun (s,i) -> s.[i]
tail = fun (s,i) -> (s, i+1)
}
///Extracts the option value associated with a node.
let node_value = function
| TNode (ov,_) -> ov
///Extracts the map representing connections from the current trie node to sub-trees.
let node_map = function
| TNode (_, m) -> m
///Determines whether a trie is empty
let is_empty tn = Map.isEmpty (node_map tn)
///Empty trie.
let empty_trie = TNode (None, Map.empty)
/// <summary>
/// Find a sub-trie.
/// </summary>
/// <param name="tn">The current trie node.</param>
/// <param name="k">The key.</param>
let find_subtrie tn k =
try
Map.find k (node_map tn)
with
not_found -> empty_trie
/// <summary>
/// Update the trie.
/// </summary>
/// <param name="m">The iteration module.</param>
/// <param name="tn">The trie node.</param>
/// <param name="ks">a sequence of the key elements</param>
/// <param name="v">Option containing the element</param>
let add m tn ks v =
let rec upd tn' ks' =
if(m.eos ks') then
TNode(Some v, (node_map tn'))
else
let k = (m.head ks') in
let ov = node_value tn' in
let tn'' = upd(find_subtrie tn' k)(m.tail ks') in
TNode(ov, Map.add k tn'' (node_map tn'))
in
upd tn ks
/// <summary>
/// Lookup the option value associated with a string
/// </summary>
/// <param name="m">The iteration module.</param>
/// <param name="tn">The trie node.</param>
/// <param name="ks">a sequence of the key elements</param>
let lookup m tn ks =
let rec lv tn' ks' =
if(m.eos ks') then
node_value tn'
else
let k = (m.head ks') in
lv(find_subtrie tn' k)(m.tail ks')
in
lv tn ks
/// <summary>
/// Determine whether or not a specific work is valid in the trie by a simple use of the lookup function.
/// </summary>
/// <param name="m">The iteration module.</param>
/// <param name="tn">The trie node.</param>
/// <param name="ks">a sequence of the key elements</param>
let mem m tn ks =
match(lookup m tn ks) with
| Some _ -> true
| None -> false
/// <summary>
/// Determines the suffix of a string
/// </summary>
/// <param name="s">The string to find the suffix of.</param>
/// <param name="i">The starting point of the suffix.</param>
let suffix(s:String,i) = s.Substring(i,(String.length s - i))
/// <summary>
/// Computes the set of words defined by a trie node if we follow any valid character from that node, and then try to follow a specific char sequences.
/// </summary>
/// <param name="pfx">The prefix.</param>
/// <param name="trie">The trie node.</param>
/// <param name="wi">Word index.</param>
/// <param name="words">The words.</param>
let strings_with_suffix pfx trie wi words =
let accumulate_paths c trie' ws =
if (mem siterm trie' wi) then
Set.add (pfx + (string c) + (suffix wi)) ws
else
ws
in
//THIS IS WHERE THINGS APPEAR TO BE GOING WRONG
Map.fold accumulate_paths (node_map trie) words
/// <summary>
/// Spelling correction suggestions.
/// </summary>
/// <param name="trie">The trie.</param>
/// <param name="word">The mispelled word.</param>
let suggestions trie word =
let rec paths_around_char pfx trie wi words =
if (siterm.eos wi) then
strings_with_suffix pfx trie ("", 0) words
else if (is_empty trie) then
words
else
let c = siterm.head wi in
let wi' = siterm.tail wi in
let trie' = find_subtrie trie c in
let ins_ws = strings_with_suffix pfx trie wi words in
let rep_ws = strings_with_suffix pfx trie wi' ins_ws in
let del_ws = if (mem siterm trie wi') then
Set.add (pfx + (suffix wi')) rep_ws
else
rep_ws
in
paths_around_char (pfx + (string c)) trie' wi' del_ws
in
paths_around_char "" trie (word, 0) Set.empty
Заранее спасибо,
Bob