3

My goal is to replace all literal sub-strings in a given string.

  (defun translate (str)
    (concat (mapcar (lambda(cons)
              (replace-in-string (car cons) (cdr cons) str))
            '(("ä" "ae")
              ("ö" "oe")
              ("ü" "ue")
              ("ß" "ss")))))
  )

  (defun replace-in-string (what with in)
    (replace-regexp-in-string (regexp-quote what) with in nil 'literal))

translate should replace all ä's by ae's etc. but it doesn't. Can you please tell me what is wrong?

See this discussion for replace-in-string.

  • 2
    1. You have an extra ) after your first defun. 2. Your cdr should be cadr. 3. I doubt that you want to perform a separate replacement for each replacement pair, and list the results, getting a list of STR with each of the replacements separately. I.e., (with the cadr correction) the mapcar returns ("aeöüß" "äoeüß" "äöueß" "äöüss"). 4. You cannot use concat on such a list returned by mapcar. See @xuchunyang's answer for an answer. – Drew Jul 4 '15 at 18:48
1
(defun translate (str)
  (dolist (cons '(("ä" . "ae")
                  ("ö" . "oe")
                  ("ü" . "ue")
                  ("ß" . "ss")) str)
    (setq str (replace-in-string (car cons) (cdr cons) str))))

;; Try it
(translate "ä's => ß's")
;; => "ae's => ss's"
  • Thanks! (translate "ä-ö-ü-ß") returns "ae-oe-ue-ss". But because it modifies the string str in the loop one has to be careful when defining the translation map. Do you see it? – Andreas Spindler Jul 4 '15 at 16:23
  • @AndreasSpindler the solution does not answer the question? – Name Jul 4 '15 at 18:13
  • Basically, yes. On the other hand, if you e.g. define something like '(("x" . "y") ("y" . "z")) as the translation map you end up with all x's being translated to z's, not y's as the map actually proposes. Therefore my immediate comment. Despite this it's a good solution and I'll accept it. Thanks! – Andreas Spindler Jul 4 '15 at 19:34
2
(defun translate (str alist)
  (replace-regexp-in-string
   (regexp-opt (mapcar 'car alist))
   (lambda (match)
     (cdr (assoc match alist)))
   str))
2

This was written late at night and requires more substantial testing, but it passes simple tests:

(require 'strie)

(defun my/translate (input substitutes)
  (let ((trie
         (cl-loop with trie = (strie-new)
                  for (prefix . replacement) in substitutes do
                  (strie-add trie prefix replacement)
                  finally (cl-return trie))))
    (cl-labels ((%child (trie s from to)
                        (strie-get-child trie (substring-no-properties s from to))))
      (with-output-to-string
        (cl-loop with i = 0 while (< i (length input)) do
                 (let ((match 
                        (cl-loop with backtrack = nil
                                 for j from i below (length input)
                                 for child = (%child trie input j (1+ j))
                                 then (%child child input j (1+ j))
                                 do
                                 (cl-destructuring-bind (has-value value next)
                                     (or child '(nil nil nil))
                                   (when has-value
                                     (push (cons (substring-no-properties input i (1+ j)) value)
                                           backtrack))
                                   (unless next (cl-return (car backtrack))))
                                 finally (cl-return (car backtrack)))))
                   (if match
                       (progn
                         (princ (cdr match))
                         (cl-incf i (length (car match))))
                     (princ (substring-no-properties input i (1+ i)))
                     (cl-incf i))))))))

(my/translate "abcd-abc-ab-a" '(("abcd" . "1") ("abc" . "2") ("ab" . "3") ("a" . "4")))

"1-2-3-4"

This function will replace the longest possible match.

  • Wow. Looks intimidating, to be honest. It seems as if you're somehow attempting to find the stem of all strings, but then the solution would reach more in the lexical corner. Could you elaborate a bit why package trie is necessary? – Andreas Spindler Jul 5 '15 at 9:44
  • @AndreasSpindler trie is also known as prefix tree. There are two kinds of prefix trees, some store offsets in the original string, others store the values themselves (the first kind is more efficient memory-wise), but this trie is of the second kind (easier to implement). The idea behind this data-structure is to store common prefix of all given strings. Doing so avoids repeating searches for common prefix, if you have to search for multiple sub-strings. So, unlike repeated replace-in-string, it will replace each character of the original string at most once. It will also always choose – wvxvw Jul 5 '15 at 12:18
  • to replace the longest possible match (i.e. if you can replace both "ab" and "abc" sub-strings, it will chose to replace "abc"). Here's a Wiki page on tries: en.wikipedia.org/wiki/Trie – wvxvw Jul 5 '15 at 12:18
2

Conclusion so far.

xuchunyang's translate:

(defun translate (str alist)
  (dolist (cons alist str)
    (setq str (replace-in-string (car cons) (cdr cons) str))))

(translate "a b c" '(("a" . "b") ("b" . "c") ("c" . "d")))
"d d d"

We could call this the intrusive version.

politza's translate:

(defun translate (str alist)
  (replace-regexp-in-string
   (regexp-opt (mapcar 'car alist))
   (lambda (match) (cdr (assoc match alist))) str))

(translate "a b c" '(("a" . "b") ("b" . "c") ("c" . "d")))
"b c d"

We could call this the non-intrusive version.

wxvxw's version is not included, mostly because I haven't installed trie. But it sounds as if his idea scales better (speed) in case of large/complex translation maps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.