Back to Questions
1.3k
views4
comments
Lexical trees - Can I make this better?
f#

I was trying to represent a lexical tree for dictionaries. The root data structure is as follows:

1
2

type lex_node = Letter of char * bool * lex_tree
and lex_tree = lex_node list;;

The boolean marks whether or not this node contains the end of a word. So if you're looking for a word in the dictionary, you just start at the top and scan down comparing successive indices of your word. Once you've reached the end of you're word, if you've still found corresponding matches in the tree for every letter, you check the boolean. If it's true the dictionary contains this word, otherwise it doesn't.

I wrote some functions to check whether a word exists in a lextree, and one to insert words into a lextree. I was hoping someone could take a look and see if these functions can be improved. I only included the insert function and its dependencies since otherwise the listing would be too long, and also it ws the most difficult to write, because due to the immutable requirement, adding a word to the dictionary means ripping out the entire path from the root, since at some point you're going to have to add a child to one of the nodes somewhere in the middle. I guess this is a common problem in designing immutable data structures though. Also, I originally wrote this in Ocaml, hoping to port it over to F# after the fact just to get a feel for some of the differences / strengths of F#, but I could find no obvious areas for improvement, either performance wise or even aesthetically. So comments on that would be appreciated too :P 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

type lex_node = 
    Letter of char * bool * lex_tree
and lex_tree = lex_node list;;

(*builds a tree for a portion of a given word*)
let rec make_word word index = 
    if (index >= String.length word) then 
        failwith "Invalid word, index >= String.length word"
    else if (index=(String.length word-1)) then
        Letter ( word.[index], true, [] )
    else
        Letter (word.[index], false, (make_word word (index+1))::[]);;

(*insert a single word into a tree and return the new tree*)
let rec insert_word tree word = 
    let word_len = String.length word in

    (*scan finds a node with a given letter in the list of nodes, and rips out the found node, keeping the rest of the list intact*)
    let scan l letter = 
        let comp (Letter(x,_,_)) = (x=letter) in
            match (List.partition comp l) with
                ([],_) -> (None, l)
                | (x,second) -> (Some (List.hd x), second) in 
    (*given a single node, internal_consume inserts the portion of the word starting at index 'index'*)
    let rec consume root (word:string) index = 
        let cur_letter = word.[index] in
        match root with
            Letter(x,_,_) when (x<>cur_letter) -> 
                failwith "Error, wrong dictionary. "               (*function requires tree.letter = word.[index]*)
            | Letter(x,_,y) when (index=word_len-1) -> Letter(x,true,y)      (*if this node successfully ends the word, mark end flag*)
            | Letter(_,mark,children) ->        (*otherwise look for a child that matches the next letter*)
                Letter(cur_letter, mark, 
                    match (scan children word.[index+1]) with
                        (None, _) -> (make_word word (index+1))::children
                        | (Some x, remain) -> (consume x word (index+1))::remain) in
    let (ripped, remain) = (scan tree word.[0]) in
        match ripped with
            None -> (make_word word 0)::remain
            | Some (Letter(a,b,c) as x) -> (consume x word 0)::remain


(*Given a list of word, build a tree containing all of these words*)
let construct words = 
    List.fold_left insert_word [] words;;

(*Two utilitiy functions to decide which subset of words in a given list
  is / isn't in a lextree*)
let verify_in tree words = (fst (List.partition (exists tree) words));;
let verify_out tree words = (snd (List.partition (exists tree) words));;
.

Why choose this representation? It seems like it is very inefficient both for creation (you must rebuild the entire tree for every insert) and lookup (each letter takes O(n), well ok, O(26)). It is interesting to experiment with such structures for practice working with immutable data structures, but I think a real application would be better served by a mutable data structure (which would be easier to author, and give better run-time performance).

By on 12/6/2008 2:22 PM ()

Why choose this representation? It seems like it is very inefficient both for creation (you must rebuild the entire tree for every insert) and lookup (each letter takes O(n), well ok, O(26)). It is interesting to experiment with such structures for practice working with immutable data structures, but I think a real application would be better served by a mutable data structure (which would be easier to author, and give better run-time performance).

The reason you gave about interesting to experiment for practice working with immutable data structures :P

Since Ocaml has been around for a while longer than F#, there's more learning material about it. Particularly books with exercises, which I find is the best way to feel like you have practical experience working with a language even when you don't. I found this one at the end of chapter 2 of the freely available Ocaml ebook.

By on 12/6/2008 3:27 PM ()

Ok, if just for practice, then here is my stab at it (I need practice with this too :) ).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#light

open System.Text

type LexNode = Node of char * bool * LexNode list  
// throughout, I'll use "lnl" for a variable of type "LexNode list"

// handy helper
let Char (Node(c,_,_)) = c

// Note: functions below are not tail recursive; deep tree could stack overflow

// useful display of data structure, I can't imagine debugging/verifying without it
let PrettyPrint lnl =
    let acc = new StringBuilder()
    let rec PrettyPrint lnl revPrefix depth =
        let spaces = new string(Array.create depth ' ')
        let Word c revPrefix = new string(c::revPrefix |> List.rev |> Array.of_list)
        match lnl with
        | [] -> ()
        | (Node(c,isWord,children)) :: t ->
            if isWord then
                acc.AppendFormat("{0}{1}            {2}\n", spaces, c, Word c revPrefix) |> ignore
            else
                acc.AppendFormat("{0}{1}\n", spaces, c) |> ignore
            PrettyPrint (children |> List.sort_by Char) (c::revPrefix) (depth+1)
            PrettyPrint t revPrefix depth
    PrettyPrint (lnl |> List.sort_by Char) [] 0
    acc.ToString()
            
// test the printer
let example = [ Node('t', false, [
                    Node('h', false, [
                        Node('e', true, [
                            Node('n', true, [])])])])
                Node('h', false, [
                    Node('i', true, [])])]
printfn "%s" (PrettyPrint example)

// given lnl, return a new lnl with word inserted
let Insert (word:string) lnl =
    let rec Insert lnl letters =
        match letters with
        | [] -> lnl
        | c :: suffix ->
            let isLastChar = List.is_empty suffix
            let same,others = lnl |> List.partition (fun x -> c = Char x)
            let newSame =
                match same with
                | [] -> Node(c, isLastChar, Insert [] suffix)
                | [Node(_,isWord,children)] -> Node(c, isWord || isLastChar, Insert children suffix)
                | _ -> failwith "there should not be multiple entries in list with same char"
            newSame :: others
    Insert lnl (word |> Seq.to_list)

let example2 =
    []
    |> Insert "then"
    |> Insert "the"
    |> Insert "hi"
    |> Insert "high"

printfn "-------------"
printfn "%s" (PrettyPrint example2)
By on 12/6/2008 4:29 PM ()

Heh, I can't believe I didn't think to convert the string to a char list first. That was one of the more annoying implementation aspects when I was doing mine, passing the index around through the recursion and having to index the string, pattern matching on the string makes it much simpler.

The lack of tail recursion bothered me at first, but I guess it's forgivable in this example, unless you're doing a dictionary for Icelandic or something where words can be extremely long.

By on 12/6/2008 5:04 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper