# Multiway string substitution

**URL:** <https://discourse.julialang.org/t/multiway-string-substitution/102345>\
**Category:** General Usage\
**Tags:** strings, regex, algorithm\
**Created:** [August 1, 2023, 9:11am UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345 "2023-08-01T09:11:40Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![Denis\_Ivanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denis_ivanov/32/52607_2.png) [@Denis\_Ivanov](https://discourse.julialang.org/u/Denis_Ivanov)\
**Post date:** [August 1, 2023, 9:11am UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/1 "2023-08-01T09:11:40Z")

</div>

I have set an ambitious goal of modeling some [Wolfram Physics Project](https://www.wolframphysics.org/) features into Julia. Because actually, Julia works faster and more efficiently, while the subject is very interesting.  
A bit later I will be happy to present a beta version of a small package in which everyone can participate.

In the meantime, I’d like to ask a few questions.

One of the key concepts in WPP is the [Multiway system](https://www.wolframphysics.org/technical-introduction/the-updating-process-for-string-substitution-systems/string-substitution-systems/). Its essence is simple.

Let there be an initial string `"A"` and dictionary of rules: `("A" => "BBB", "BB" => "A").`  
Using them, we first get an obvious result: “A” → “BBB”  
But the next step we can do in several ways (greedy method, first occurence method etc), of which I am interested in Multiway method, when we _collect all possible results_, so: “BBB” → [“AB”, “BA”] (this is like the Multiverse).

Looks like Julia’s built-in features don’t allow this. We will have to make an array from the string and analyze it manually. In this case, probably should abandon the strings at all?  
But maybe I don’t know all the possibilities, so I’ll take any advice.

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [August 1, 2023, 9:50am UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/2 "2023-08-01T09:50:28Z")

</div>

Here’s how to collect all possible matches.

```julia
julia> matches = collect(eachmatch(r"BB", "BBB", overlap=true))
2-element Vector{RegexMatch}:
 RegexMatch("BB")
 RegexMatch("BB")

julia> matches[1].offset
1

julia> matches[2].offset
2

```

Don’t know about carrying out the replacements, though.

---

<div class="post-metadata">

**Author:** ![Denis\_Ivanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denis_ivanov/32/52607_2.png) [@Denis\_Ivanov](https://discourse.julialang.org/u/Denis_Ivanov)\
**Post date:** [August 1, 2023, 10:39am UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/3 "2023-08-01T10:39:05Z")

</div>

Thank you, but I’d like to avoid Regex. Because of the difficulties with the replacement and because it is a completely different ideology

---

<div class="post-metadata">

**Author:** ![raman\_kumar](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/raman_kumar/32/26782_2.png) [@raman\_kumar](https://discourse.julialang.org/u/raman_kumar)\
**Post date:** [August 1, 2023, 10:52am UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/4 "2023-08-01T10:52:58Z")

</div>

Regex are very good and fast way to match strings.

---

<div class="post-metadata">

**Author:** ![Denis\_Ivanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denis_ivanov/32/52607_2.png) [@Denis\_Ivanov](https://discourse.julialang.org/u/Denis_Ivanov)\
**Post date:** [August 1, 2023, 10:56am UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/5 "2023-08-01T10:56:24Z")

</div>

Hmm, ok, may be I should do it with Regex, but what about replacement (and to collect different ways)?  
And! What is maximal string length that not overload Regex searching?

---

<div class="post-metadata">

**Author:** ![algunion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/algunion/32/51630_2.png) [@algunion](https://discourse.julialang.org/u/algunion)\
**Post date:** [August 1, 2023, 1:26pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/6 "2023-08-01T13:26:09Z")

</div>

> [@Denis\_Ivanov](#):
>
> Looks like Julia’s built-in features don’t allow this. We will have to make an array from the string and analyze it manually. In this case, probably should abandon the strings at all?  
> But maybe I don’t know all the possibilities, so I’ll take any advice.

I am also not aware of any Julia built-in feature that supports this.

However, you might achieve something quite elegant with a little tinkering and the right data structures.

I suggest taking a look at [this](https://juliacollections.github.io/DataStructures.jl/latest/).

I would also consider a domain modeling approach where you can create your own data type and maybe implement the [AbstractTrees](https://juliacollections.github.io/AbstractTrees.jl/stable/) interface over it.

As a general rule, if performance is paramount and you have a limited set of rules, and all the `key` / `replacement` values are known at the compile time, then you might want to give up the `String` anyway and replace it with a more memory friendly type (you might still generate a `String` output as final result).

---

<div class="post-metadata">

**Author:** ![contradict](https://avatars.discourse-cdn.com/v4/letter/c/ac91a4/32.png) [@contradict](https://discourse.julialang.org/u/contradict)\
**Post date:** [August 1, 2023, 2:03pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/7 "2023-08-01T14:03:21Z")

</div>

This package may also provide some inspiration: [GitHub - BioJulia/Automa.jl: A julia code generator for regular expressions](https://github.com/BioJulia/Automa.jl)

I’m not sure it does what you want, but using similar techniques to write a “Rule to Julia” compiler might be a performant (though not necessarily simple) way to do what you want.

---

<div class="post-metadata">

**Author:** ![greatpet](https://avatars.discourse-cdn.com/v4/letter/g/e495f1/32.png) [@greatpet](https://discourse.julialang.org/u/greatpet)\
**Post date:** [August 1, 2023, 3:36pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/8 "2023-08-01T15:36:57Z")

</div>

It’s not difficult to do the replacements once the matches are found, with a little code:

```julia
function replacements_all(a::AbstractString, b::Pair{Regex, <:SubstitutionString})
    (r, s) = b
    matches = eachmatch(r, a, overlap = true)
    results = String[]
    for m in matches
        s1 = @views a[1:(m.offset - 1)]
        s2 = @views a[m.offset:end]
        s2replaced = replace(s2, r => s, count = 1)
        push!(results, s1 * s2replaced)
    end
    results
end

```

Test:

```julia
julia> replacements_all("BBBB", r"BB" => s"A")
3-element Vector{String}:
 "ABB"
 "BAB"
 "BBA"

```

There is some inefficiency here since `replace` searches the regex pattern again.

---

<div class="post-metadata">

**Author:** ![Denis\_Ivanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denis_ivanov/32/52607_2.png) [@Denis\_Ivanov](https://discourse.julialang.org/u/Denis_Ivanov)\
**Post date:** [August 1, 2023, 4:24pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/9 "2023-08-01T16:24:40Z")

</div>

Yes, your answer is very close to what I’ve found.  
`AbstractTrees` is musthave for Multiway System, thank you!  
Sooner I’ll publish a small “SubstitutionSystem” project and will be glad of your advice!

---

<div class="post-metadata">

**Author:** ![Denis\_Ivanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denis_ivanov/32/52607_2.png) [@Denis\_Ivanov](https://discourse.julialang.org/u/Denis_Ivanov)\
**Post date:** [August 1, 2023, 4:50pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/10 "2023-08-01T16:50:34Z")

</div>

After thinking, I realized that I would have to use Regex, because it is difficult to organize a proper search in `Vector`

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [August 1, 2023, 8:54pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/11 "2023-08-01T20:54:28Z")

</div>

```julia
function multisbs(str,sstr, s)
    res=String[]
    fp=findfirst(str, s)
    while !isnothing(fp)
        push!(res,s[1:first(fp)-1]*sstr*s[last(fp)+1:end])
       #push!(res,s[1:fp.start-1]*sstr*s[fp.stop+1:end])
        fp=findnext(str, s,first(fp)+1)
    end
    res
end

julia> multisbs("BBA","A","BBABBA")
2-element Vector{String}:
 "ABBA"
 "BBAA"

julia> multisbs("BB","A","BBABBA")
2-element Vector{String}:
 "AABBA"
 "BBAAA"

julia> multisbs("BB","A","BBBBA")
3-element Vector{String}:
 "ABBA"
 "BABA"
 "BBAA"

julia> multisbs("BB","A","BBBBB")
4-element Vector{String}:
 "ABBB"
 "BABB"
 "BBAB"
 "BBBA"

```

---

<div class="post-metadata">

**Author:** ![Denis\_Ivanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denis_ivanov/32/52607_2.png) [@Denis\_Ivanov](https://discourse.julialang.org/u/Denis_Ivanov)\
**Post date:** [August 4, 2023, 3:24pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/12 "2023-08-04T15:24:18Z")

</div>

This is really great! Now I’m trying to adapt it for vectors,  
but the way `findfirst` works for `Vector` bother me (

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [August 4, 2023, 4:24pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/13 "2023-08-04T16:24:50Z")

</div>

> [@Denis\_Ivanov](#):
>
> This is really great! Now I’m trying to adapt it for vectors,

what do you mean exactly? vector{UInt8} instead of strings or something?

---

<div class="post-metadata">

**Author:** ![Denis\_Ivanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denis_ivanov/32/52607_2.png) [@Denis\_Ivanov](https://discourse.julialang.org/u/Denis_Ivanov)\
**Post date:** [August 4, 2023, 4:39pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/14 "2023-08-04T16:39:33Z")

</div>

The problem is just find sub-vector in vector! How to make `my_findfirst_vec`,  
so `my_findfirst_vec([1, 1], [0, 1, 0 , 0, 1, 1, 1, 1])` return `5:6` (0\_0)  
I cannot find such recipe in community

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [August 4, 2023, 4:46pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/15 "2023-08-04T16:46:27Z")

</div>

if you damain is contained in UInt8, you can do

```julia
findfirst([0x1, 0x1], UInt8[0, 1, 0 , 0, 1, 1, 1, 1]) 

```

or more generally

```julia
using IterTools
findfirst(==((1,1)), collect(partition([0, 1, 0 , 0, 1, 1, 1, 1],2,1))) 

```

```julia
function searchfirstsubvec(v,sv)
    l=length(sv)-1
    for i in eachindex(v)
        sv==v[i:i+l] ? (return i:i+l) : continue
    end
end

```

---

<div class="post-metadata">

**Author:** ![abulak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abulak/32/28314_2.png) [@abulak](https://discourse.julialang.org/u/abulak)\
**Post date:** [August 5, 2023, 11:07am UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/16 "2023-08-05T11:07:11Z")

</div>

If you know all replacement rules in advance the data structure you’re looking for is Aho-Corasik automaton (sometimes known as index automaton). It allows e.g. to find all matches in time linear with the length of the input string.

However it is not clear to me how do you derive `A` → `[AB, BA]`. To me your rules generate an infinite chain (or rather a tree) of replacements which you could in theory traverse breadth-first. The question is what do you want to obtain?

(to avoid infinite chains/branches one usually adds shift-invariant well-order on the free monoid of strings (e.g. shorter-then-lexicographical) – this of course is not trouble free, as choosing the right order for your application is a problem of its own 😉

---

<div class="post-metadata">

**Author:** ![Denis\_Ivanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denis_ivanov/32/52607_2.png) [@Denis\_Ivanov](https://discourse.julialang.org/u/Denis_Ivanov)\
**Post date:** [August 6, 2023, 2:55pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/17 "2023-08-06T14:55:07Z")

</div>

I’m going to implement functions [SubstitutionSystem](https://reference.wolfram.com/language/ref/SubstitutionSystem.html) and [MultiwaySystem](https://resources.wolframcloud.com/FunctionRepository/resources/MultiwaySystem) from Wolfram ecosystem on Julia.  
In some ways they are similar to Aho–Corasick algorithm, but in many ways they are not.

First of all, there are no problems with infinite string expansion and numbers of replacement results.  
In the near future I will post a link to Git, and I really hope that Julia’ community will help me to create a good package!

---

<div class="post-metadata">

**Author:** ![abulak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abulak/32/28314_2.png) [@abulak](https://discourse.julialang.org/u/abulak)\
**Post date:** [August 6, 2023, 8:15pm UTC](https://discourse.julialang.org/t/multiway-string-substitution/102345/18 "2023-08-06T20:15:07Z")

</div>

Aho-Corasik is just (just?!) a data structure that allows you to find all occurrences of LHSes in a given input string in optimal time. Here by “string” I mean anything that is linearly ordered. I’m pretty sure Mathematica uses it behind the scenes to describe the “evolution of MultiwaySystem”. After reading their docs it’s still very much unclear to me what does it really mean, but hey, maybe your package is going to do a better job! I’m looking forward to reading it!