0
$\begingroup$

Although I was slightly taken aback when I came across the behaviour, the following examples are perfectly in line with the way StringReplace is described in the documentation:

StringReplace["NTGQF", (#1 -> " " <> #1 <> " " &) /@ {"TGQF", "N", "NT"}]

returns:

" N  TGQF " 

And:

StringReplace["NTGQF", (#1 -> " " <> #1 <> " " &) /@ {"TGQF", "NT", "N"}]

returns:

" NT GQF"

That is: for each substring StringReplace attempts replacements in the order the patterns are given. But the overall resulting behaviour does not guarantee that the string is going to be parsed according to that order.

Within a parsing context though, I would like to enforce a priority of tokens regardless of the direction Mathematica breaks down the string to create the substrings. That is I would like to get the first answer.

Is there a straight-forward way of doing this?

$\endgroup$
2
$\begingroup$

Maybe this can help:

rules = (#1 -> " " <> #1 <> " " &) /@ {"TGQF", "NT", "N"};
Fold[StringReplace, "NTGQF", rules]

Using Fold, you can apply StringReplace respecting the order defined by rules.

You can also see your transformations states using FoldList.

FoldList[StringReplace, "NTGQF", rules]

{"NTGQF", "N TGQF ", "N TGQF ", " N TGQF "}

$\endgroup$
  • $\begingroup$ As said, my question might not be specific enough. Your answer will always tokenise to the right-most token, which is not what I intend. I intend to stop at the the first valid token for any substring in the string and then start all over again. Your answer points probably towards the final solution. . $\endgroup$ – Trad Dog Dec 16 '15 at 14:09
  • $\begingroup$ Not sure why I cannot edit my comment. My question might not be specific enough. Your answer will always tokenise to the right-most token, which is not what I intend. I intend to stop at the the first valid token for any substring in the string and then start all over again, removing the matched token. Your answer points probably towards the final solution however. At any rate, both yours and Sjoerd's seems to indicate I am not overlooking a built-in Mathematica feature. $\endgroup$ – Trad Dog Dec 16 '15 at 14:18
  • $\begingroup$ @TradDog Can you edit your question to give us a better example? Put the rules input and the desired output. $\endgroup$ – Murta Dec 16 '15 at 14:34
1
$\begingroup$

The context is the parsing of strings. Breaking down in terminal tokens can lead to ambiguous situations where several possibilities are valid (which the grammar itself can reject but that is another issue). An example is the string "ABC", with terminals {"A","BC","ABC"}.

A unsafe solution is to rely on the order of the list of tokens for the breakdown (as an afterthought, generating all possible tokenisations is probably not that costly but I did not go down that route).

There ought to be a simple solution to the issue.

Meanwhile, here is a code whose only saving grace is that it might be doing the job. It is unecessarily complex (actually bordering horrific). I thought StringPosition and interval arithmetic would provide a nifty answer. As it turns out the API for Interval is very limited: intervals support only real numbers and lack some elementary processing functions such as a "IntervalComplement" function, which leads to a lot of code being necessary. Nonetheless I carried on with the initial idea and the resulting code yields correct results on --too-- few tests.

Retrospectively, I am not sure neither the question nor the answer are worth dwelling upon but since I started the thread I thought I ought to finish it.

noOverlapWithFirst[listInt_List] := Module[{first, rest},
  first = First@listInt;
  rest = Rest@listInt;
  Append[Select[rest, IntervalIntersection[#, first] == Interval[] &],
    first]
  ]
insertIntervals[intervals_List, list_List] := 
 If[Length[list] == 0, intervals,Union @@ KeyValueMap[Insert[intervals, #2, #1] &, 
   GroupBy[{list, (Floor[#]/2 + 
            1) & /@ (Combinatorica`BinarySearch[
             Flatten@intervals, #] & /@ 
           list)}\[Transpose], #[[2]] &] /. {{x_, n_},___, {y_, 
        m_}} -> {x, y} /. {{z_, k_}} -> {z, z}]]

tokeniseWithPriority[text_String, terminals_List] := 
 Module[{intsNonOverlap, listInt},
  listInt = 
   Interval /@ (First /@ (Select[
        StringPosition[text, #] & /@ terminals, Length[#] != 0 &]));
  intsNonOverlap = 
   Flatten[Sequence @@ #] & /@ (Sort@ 
      Nest[noOverlapWithFirst, listInt, Length[listInt]]);
  intsNonOverlap = 
   insertIntervals[intsNonOverlap, 
    Complement[Range[1, StringLength[text]], 
     Flatten@(Range @@@ intsNonOverlap)]];
  StringTake[text, intsNonOverlap]
  ]

As one test:

tokeniseWithPriority["KQ29NTGQF12UVEU", {"KQ", "NOMATCH", "TGQF", "=",
   "UVEU", "N"}]

yields:

{"KQ", "29", "N", "TGQF", "12", "UVEU"}

And:

tokeniseWithPriority["KQ29NTGQF12UVEU", {"NT", "KQ", "NOMATCH", 
  "TGQF", "=", "UVEU"}]

yields:

{"KQ", "29", "NT", "GQF12", "UVEU"}
$\endgroup$
0
$\begingroup$

Here is a more standard way of dealing with the issue:

tokenizeOneTerminal[text_String, term_String] := 
 Block[{m}, 
  m = StringReplace[text, StartOfString ~~ term ~~ x : ___ -> x]; {m, 
   If[StringMatchQ[text, m], "", term]}]
tokenizeOnceStrict[text_String, terminals : {__String}] := 
 First@NestWhile[{tokenizeOneTerminal[#[[1, 1]], First@(#[[2]])], 
     Rest[#[[2]]]} &, {{text, ""}, 
    terminals}, (Length[ #2[[2]]] != 0) && (First@#1 == First@#2) &, 
   2]
tokenizeOnce[text_String, terminals : {__String}] := 
 Block[{s = text, t = ""},
  {s, t} = tokenizeOnceStrict[s, terminals];
  If[StringLength[s] == 0 || StringLength[t] > 0, Return[{s, t}]];
  While[StringLength[s] > 0,
   t = t <> StringTake[s, 1];
   If[StringLength[s] == 1 , s = "",
    s = StringTake[s, {2, StringLength[s]}]
    ];
   If[StringLength[Last@tokenizeOnceStrict[s, terminals]] > 0, 
    Return[{s, t}]];
   ];
  Return[{s, t}]
  ]
tokenizeWithPriority[text_String, terminals : {__String}] := 
 NestWhile[
  Block[{m}, 
    m = tokenizeOnce[First@#, terminals]; {First@m, 
     Flatten[Append[Rest@#, Last@m]]}] &, {text, {}}, 
  StringLength[#[[1]]] != 0 &]

I left the previous answer as I am still suprised you could deal with the problem only with StringPosition and involving no string pattern at all. It is also 21 times faster.

$\endgroup$

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.