Find Replace Multi-Pairs Feedback Loop Problem

Find Replace Multi-Pairs Feedback Problem

If find replace pairs is done one after one, then you may end up with a substring that's not in the original input string nor in any of the find replace pairs. For example.

Input string:

• abcd

Replace Pairs:

• a → c
• cb → x

Result:

• Expected: cbcd
• Actual: xcd

Required Condition of Occurrence

2021-09-06 the non intentional replacement happens when a replace string is a superset or subset of subsequent find string.

• If superset, it always happen.
• If subset, it may happen.

Example

text is: sa

• subset situation:
• a → p
• sp → b

• superset situation:
• a → op
• p → b

Real World Example

JavaScript Example

const xx = "abcd";

const xpairs = [
  ["a", "c"],
  ["c", "d"],
];

const xresult = xpairs.reduce((a, b) => (a.replaceAll(b[0], b[1])), xx);

console.log(xresult === "dbdd");

WolframLang Example

WolframLang's find-replace function does not have this feedback problem.

StringReplace[ "abcd", {"a" -> "c","c" -> "d"} ] === "cbdd"

State of AI. Multiple String Replacement Problem

• for coders. state of artificial intelligence.
• wow. extremely impressive.
• AI answered my question of vague description.
• Told me it's called Multiple String Replacement Problem.
• and indeed, checked out.

• brave search ai bot give further detail.
• it mentioned 2-pass solution, which is what i was doing.

• https://x.com/xah_lee/status/1955076452753240545
• https://x.com/xah_lee/status/1955079335750091003

• https://x.com/xah_lee/status/1955079635559170117

Solutions

Solution 1, Use Single Regex Connected with Or, with a Dictionary for Pairs

1. Convert all find strings into a regex, connected with “or”.
2. Convert the find replace pairs into a hashtable for efficiency, for later use.
3. Do find on the regex, for each found, find the matched string, and replace it with corresponding item.

Solution 2, 2-pass. first pass replace the find strings with unique ID.

1. Generate a random unique string list, same items as the pairs.
2. Loop thru each pair and do find replace.
3. For each found, replace it by corresponding unique string.
4. Do another find replace loop thru unique string list.
5. For each found, replace it by corresponding replacement string.