Skip to content

Commit

Permalink
Merge remote branch 'thelmuth/fix-levenshtein'
Browse files Browse the repository at this point in the history
  • Loading branch information
lspector committed Oct 27, 2013
2 parents 847ac5f fa8682d commit 7fe77dd
Show file tree
Hide file tree
Showing 2 changed files with 33 additions and 37 deletions.
67 changes: 32 additions & 35 deletions src/clojush/experimental/calc.clj
Original file line number Diff line number Diff line change
Expand Up @@ -15,54 15,51 @@
[prev-row current-element other-seq pred]
(reduce
(fn [row [diagonal above other-element]]
(let [update-val
(if (pred other-element current-element)
;; if the elements are deemed equivalent according to the predicate
;; pred, then no change has taken place to the string, so we are
;; going to set it the same value as diagonal (which is the previous edit-distance)
diagonal

;; in the case where the elements are not considered equivalent, then we are going
;; to figure out if its a substitution (then there is a change of 1 from the previous
;; edit distance) thus the value is diagonal 1 or if its a deletion, then the value
;; is present in the columns, but not in the rows, the edit distance is the edit-distance
;; of last of row 1 (since we will be using vectors, peek is more efficient)
;; or it could be a case of insertion, then the value is above 1, and we chose
;; the minimum of the three
(inc (min diagonal above (peek row)))
)]
(conj row update-val)))
(let [update-val (if (pred other-element current-element)
;; if the elements are deemed equivalent according to the predicate
;; pred, then no change has taken place to the string, so we are
;; going to set it the same value as diagonal (which is the previous edit-distance)
diagonal
;; in the case where the elements are not considered equivalent, then we are going
;; to figure out if its a substitution (then there is a change of 1 from the previous
;; edit distance) thus the value is diagonal 1 or if its a deletion, then the value
;; is present in the columns, but not in the rows, the edit distance is the edit-distance
;; of last of row 1 (since we will be using vectors, peek is more efficient)
;; or it could be a case of insertion, then the value is above 1, and we chose
;; the minimum of the three
(inc (min diagonal above (peek row)))
)]
(conj row update-val)))
;; we need to initialize the reduce function with the value of a row, since we are
;; constructing this row from the previous one, the row is a vector of 1 element which
;; consists of 1 the first element in the previous row (edit distance between the prefix so far
;; and an empty string)
[(inc (first prev-row))]

;; for the reduction to go over, we need to provide it with three values, the diagonal
;; which is the same as prev-row because it starts from 0, the above, which is the next element
;; from the list and finally the element from the other sequence itself.
(map vector prev-row (next prev-row) other-seq)))

(defn levenshtein-distance
"Levenshtein Distance - http://en.wikipedia.org/wiki/Levenshtein_distance
In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences. This is a functional implementation of the levenshtein edit
distance with as little mutability as possible.
Still maintains the O(n*m) guarantee.
"
In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences. This is a functional implementation of the levenshtein edit
distance with as little mutability as possible.
Still maintains the O(n*m) guarantee."
[a b & {p :predicate :or {p =}}]
(peek
(reduce
;; we use a simple reduction to convert the previous row into the next-row using the
;; compute-next-row which takes a current element, the previous-row computed so far
;; and the predicate to compare for equality.
(fn [prev-row current-element]
(compute-next-row prev-row current-element b p))

;; we need to initialize the prev-row with the edit distance between the various prefixes of
;; b and the empty string.
(map #(identity %2) (cons nil b) (range))
a)))
(cond
(empty? a) (count b)
(empty? b) (count a)
:else (peek
(reduce
;; we use a simple reduction to convert the previous row into the next-row using the
;; compute-next-row which takes a current element, the previous-row computed so far
;; and the predicate to compare for equality.
(fn [prev-row current-element]
(compute-next-row prev-row current-element b p))
;; we need to initialize the prev-row with the edit distance between the various prefixes of
;; b and the empty string.
(range (inc (count b)))
a))))
;;;;;;

;; Lee Spector, 20130101
Expand Down
3 changes: 1 addition & 2 deletions src/clojush/pushgp/pushgp.clj
Original file line number Diff line number Diff line change
Expand Up @@ -156,8 156,7 @@
(vec))
(let [pa (doall (for [_ (range population-size)]
(make-individual
:program (random-code max-points-in-initial-program atom-generators)
:error-handler agent-error-handler)))
:program (random-code max-points-in-initial-program atom-generators))))
f (str "data/" (System/currentTimeMillis) ".ser")]
(when save-initial-population
(io/make-parents f)
Expand Down

0 comments on commit 7fe77dd

Please sign in to comment.