4
$\begingroup$


I am trying to write some kind of demonstration for coding algorithm (for prefix codes).
I have an Association that contains lists of bits (0s and 1s):

<|{"1"} -> "a", {"0", "1"} -> "b", {"0", "0"} -> "c"|>

And a list that represents a coded string (which in our example aabc):

{1,1,0,1,0,0}

And Im trying to write a code that searches for a match between a prefix (of any length) from my coded string with a key in the association (without loops). If I would use a loop I would try to find a prefix in the coded string in increasing length (first look for a match in length 1, then in 2 and so on..).
For now, my goal is to find a match, remove it from the list, and find the next matching. In case I am going wrong with this idea (in the matter of efficiency), I would thank you if you suggest me better ideas.
I have tried to search online and in the forum but without any success.
Any tip will be appreciated !
Thank you

$\endgroup$
7
  • $\begingroup$ I am not sure I understand the question, but I think you are looking for some sort of prefix tree (trie) search and retrieval and that is discussed in MSE here: "Can a Trie be implemented efficiently?". Specifically this answer should be a good start to do what you want. $\endgroup$ May 20, 2017 at 15:54
  • $\begingroup$ Thank you for your reply, I am trying to find a more simple solution for this problem. For now, I'm just trying to find a prefix that exists in the Association. Maybe a similar parallel problem will be to find the first sub-sequence that is an element in an other list. $\endgroup$
    – kobibo
    May 20, 2017 at 16:16
  • $\begingroup$ What output do you expect for the example input given? Do you want to get back "aabc"? $\endgroup$
    – Mr.Wizard
    May 20, 2017 at 16:45
  • $\begingroup$ Yes, this is my final goal. $\endgroup$
    – kobibo
    May 20, 2017 at 16:48
  • 2
    $\begingroup$ This question has to be clarified further. $\endgroup$ May 20, 2017 at 16:53

3 Answers 3

8
$\begingroup$

If you are willing to use a simple string representation, then StringReplace might be adequate for your purpose:

decode[s_] := StringReplace[s, {"1" -> "a", "01" -> "b", "00" -> "c"}]

decode["110100"]
(* "aabc" *)

decode["101100101"]
(* "abacab" *)
$\endgroup$
1
  • $\begingroup$ Works Amazing ! Thank you ! $\endgroup$
    – kobibo
    May 20, 2017 at 18:35
5
$\begingroup$

This is probably not highly efficient but I think it does what you describe.

asc = <|{1} -> "a", {0, 1} -> "b", {0, 0} -> "c"|>;
code = {1, 1, 0, 1, 0, 0};

rls = KeyValueMap[Append[#, x___] :> (Sow[#2]; {x}) &, asc] // Dispatch;

Reap[code //. rls;][[2, 1]]
{"a", "a", "b", "c"}
  • Note that I replaced string "0" and "1" in the Association with integer 0 and 1 for consistency with the coded string (code).
$\endgroup$
1
  • $\begingroup$ Thank you very much, It worked fine, but took 2 minutes to evalute for a 30kB string... $\endgroup$
    – kobibo
    May 20, 2017 at 18:36
2
$\begingroup$
asc = <|{1} -> "a", {0, 1} -> "b", {0, 0} -> "c"|>;

func[assoc_Association, code : {(1 | 0) ..}] := 
Map[assoc[#] &][SequenceCases[code, Alternatives @@ Keys@assoc]];

func[asc,{1, 1, 0, 1, 0, 0}]
(* {"a", "a", "b", "c"} *)

code = {1, 0, 1, 1, 0, 0, 1, 0, 1};
func[asc,code]
(* {"a", "b", "a", "c", "a", "b"} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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