Dynamically extract pattern unique to each string in a list of strings in bash

Viewed 146

I am trying to dynamically extract unique patterns from a list of filenames in bash.

Input list of filenames looks like this

Exp1_ML_Rep1.txt,Exp1_ML_Rep2.txt,Exp1_ML_Rep3.txt

I want to dynamically extract the strings

Rep1,Rep2,Rep3

Shown diagrammatically here:

Example1

NOTE: The input pattern can change every time e.g. another use case may be

Exp2_DT_10ng_55C_1_User1.png,Exp2_DT_10ng_55C_2_User1.png,Exp2_DT_10ng_55C_3_User1.png

In this case, I want to extract

1,2,3

Shown diagrammatically here:

Example2

What is the best way to achieve this in bash?


As recommended in the comments, I tried the following:

declare -p string1 string2

declare -- string1="ER_Rep1"
declare -- string2="ER_Rep2"

diff <(echo "$string1" ) <(echo "$string2") which returns

1c1 
< ER_Rep1 
--- 
> ER_Rep2

What I am trying to extract is Rep1,Rep2.

4 Answers

You can use GNU awk in combination with sort & uniq

echo 'Exp1_ML_Rep1.txt,Exp1_ML_Rep2.txt,Exp1_ML_Rep3.txt' | awk -v RS='[_.,]' '1' | sort | uniq -u

or

tr in combination with sort & uniq

echo 'Exp1_ML_Rep1.txt,Exp1_ML_Rep2.txt,Exp1_ML_Rep3.txt' | tr '_.,' '\n' | sort | uniq -u

produces output

Rep1
Rep2
Rep3

You can consider this awk solution:

declare -- string1="ER_Rep1"
declare -- string2="ER_Rep2"

awk -F '[_.]+' '{for (i=1; i<=NF; ++i) ++fq[$i]}
END {for (w in fq) if (fq[w] == 1) print w}' <(echo "$string1" ) <(echo "$string2")

Rep1
Rep2

This awk solution uses _ or . as field separator and stores each field in an associative array fq with the value as a number that represents frequency of occurrence of that word.

In the END block we iterate each word in fq array and print the word if frequency is equal to 1 indicating unique occurrence of that word.

I'm sure there's a better way to code this, but what I've done here is a general solution for an arbitrary number of input strings.

  • find the longest common prefix of underscore-separated substrings

    longestCommonPrefix() {
        local i prefix file found
        local -a pieces
        IFS=_ read -ra pieces <<<"$1"
        for ((i = ${#pieces[@]} - 1; i > 0; i--)); do
            prefix=$(IFS=_; echo "${pieces[*]:0:i}_")
            found=true
            for file in "${@:2}"; do
                if [[ $file != "$prefix"* ]]; then
                    found=false
                    break
                fi
            done
            if $found; then
                echo "$prefix"
                return
            fi
        done
    }
    
  • find the longest common suffix (of plain characters)

    longestCommonSuffix() {
        local i suffix file found
        for ((i = ${#1}; i > 0; i--)); do
            suffix=${1: -i}
            found=true
            for file in "${@:2}"; do
                if [[ $file != *"$suffix" ]]; then
                    found=false
                    break
                fi
            done
            if $found; then
                echo "$suffix"
                return
            fi
        done
    }
    
  • and put them together

    uniqueStrings() {
        local prefix=$(longestCommonPrefix "$@")
        set -- "${@/#"$prefix"/}"
        local suffix=$(longestCommonSuffix "$@")
        printf '%s\n' "${@/%"$suffix"/}"
    }
    

Then

$ uniqueStrings Exp1_ML_Rep1.txt Exp1_ML_Rep2.txt Exp1_ML_Rep3.txt
Rep1
Rep2
Rep3

and

$ uniqueStrings Exp2_DT_10ng_55C_1_User1.png Exp2_DT_10ng_55C_2_User1.png Exp2_DT_10ng_55C_3_User1.png
1
2
3

A couple of other examples:

# nothing in common, should return the input strings
$ uniqueStrings foo bar baz
foo
bar
baz

$ uniqueStrings x_foo13 x_bar13 x_baz13 x_qux13
foo
bar
baz
qux

Works with bash v3.2+

Looking at a solution similar to the one proposed by @glennjackman:

  • find the common prefix
  • find the common suffix
  • strip off the common prefix/suffix and what's left is the difference

Assumptions:

  • list of filenames is provided as a comma-delimited string
  • variable number of filenames
  • do character-by-character comparisons
  • no delimiters
  • assumes a single 'difference' made up of contiguous characters, eg, when comparing aBcDe and aXcYe we do not consider c to be common, so the difference will be reported as BcD and XcY

One idea using awk, which should have some performance improvement over bash-level looping:

awk '

# function to return an absolute value of a number

function abs(v) { return v < 0 ? -v : v }

# function to determine if each string has the same character at a given offset;
# return 0 if "no", return 1 if "yes"

function equal() {

    for ( i=1; i<=n; i++ ) {
        pos = offset <= 0 ? length(fname[i]) + offset : offset
        x   = substr(fname[i],pos,1)
        if ( i == 1 )    curr = x
        if ( x != curr ) return 0
    }
    return 1
}

# for now assume strings input using a here-string, and strings are delimited by a comma

FNR==1 { n=split($0,fname,",")
         exit                              # skip to END processing
       }

END {
    # twice through the outer "for" loop:
    #    op =  1 => prefix processing
    #    op = -1 => suffix processing
    # "op" will be used to increment/decrement our offset pointer to
    # perform the character-by-character comparison

    for ( op=1; op>=-1; op=op-2 ) {
        offset = op == 1 ? 1 : 0           # determine initial offset based on op (prefix vs suffix)

        # if all strings have the same character @ a given offset then update our pfx/sfx pointers

        while ( equal() && abs(offset) <= length(fname[1]) ) {
            if ( op == 1 ) pfx = offset
            else           sfx = offset

            offset = offset + op           # go to next offset
        }
    }

if ( pfx == "" ) pfx=0                     # if no common prefix, default to 0
if ( sfx == "" ) sfx=1                     # if no common suffix, default to 1

# use substr() and our pfx/sfx offsets to display the difference

for ( i=1; i<=n; i++ )
    print substr(fname[i], pfx+1, length(fname[i]) - pfx - 1 + sfx )

}' <<< "${in}"

NOTES:

  • a bit verbose at this point; may be able to streamline a bit ...
  • code could be modified to work directly with a 'normal' list of files (eg, pipe output from find into awk); one idea would be to process just the first record (FNR==1) and stuff FILENAME into the array

Test results:

# in='Exp1_ML_Rep1.txt,Exp1_ML_Rep2.txt,Exp1_ML_Rep3.txt'
1
2
3

# in='Exp2_DT_10ng_55C_1_User1.png,Exp2_DT_10ng_55C_2_User1.png,Exp2_DT_10ng_55C_3_User1.png'
1
2
3

# in='x_foo13,x_bar13,x_baz13,x_qux13'
foo
bar
baz
qux

# in='x_foo13,x_bar13,x_baz13,x_abcde23'
foo1
bar1
baz1
abcde2

# in='abcde.123,abcde.123,abcde.123'    # identical
                  # three
                  # blank
                  # lines

# in='abc,def,123456,xyz$$'             # nothing in common
abc
def
123456
xyz$$
Related