Find prefix of list in Association

Question

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

Answer 1

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" *)

Answer 2

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).

Answer 3

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"} *)