Hello all,
I've implemented the levenshtein measure in clojure and am quite happy
with it except that I run into stack overflows if I hand over long
strings. My current solution looks like this:
-- snip start --
(declare levenshtein-rec)
(declare change-cost)
(defn levenshtein
"Compute Levenshtein distance between 2 strings"
[a b]
(binding [change-cost (fn [x y] (if (= x y) 0 1))
levenshtein-rec (memoize
(fn [x y]
(cond
(empty? x) (count y)
(empty? y) (count x)
:default
(min
(+ 1 (levenshtein-rec (rest x) y)) ; deletion
(+ 1 (levenshtein-rec x (rest y))) ; addition
(+ (change-cost (first x) (first y))
(levenshtein-rec (rest x) (rest y))) ;
change
))
)
)
]
(levenshtein-rec a b)))
;;;(levenshtein "kitten" "sitting")
;;;(time (levenshtein (apply str (repeat 300 "kitten ")) (apply str
(repeat 300 "sitting"))))
-- snip end --
Now what I've done to overcome that limitation was to transform the
function from above manually into continuation passing style (CPS),
adapted it to be ready for trampolining (return in certain places
functions instead of evaluating them) and added memoization. The
result is extremely ugly and can be seen here:
https://gist.github.com/880873
I did not look yet into the clojure libraries for automatic CPS
transformation, but I am nearly certain that these libraries will not
take care of adapting the result to be ready for trampolining and
definitely will not take care of memoization.
Would somebody on the list have a proposal on how to create such a
solution simpler and nicer? Especially how would you apply memoization
easily in CPS style?
I've found an article on the web where somebody did something in that
direction in F#:
http://www.patrickdewane.com/2009/02/continuation-passing-style-and-memoization-part-2.html
Many thanks and best regards,
Christian
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
