How to filter out a set of strings A from a set of strings B using Bash

Question

Hi,

I have a list of strings which I want to remove from a super set of another strings, not in a any specific order and thus constructing a new set. Is that doable in Bash?

Answer 1

I think you'll have to at least characterize the parameters of the subset of strings you want to extract. If it's textfield-like data, though, look into awk.

Answer 2

This uses grep to see if a word has to be removed, but that's not pure BASH and it's probably faster than the other option (see below)

#!/bin/bash
REMOVE="package-x86 test0 hello world"
WORDBAG="computer hello sizeof compiler world package-x86 rocks test0"
OFS=$IFS
IFS=" "
WORDBAG_ARRAY=($WORDBAG)
IFS=$OFS
RESULT=""

for str2 in ${WORDBAG_ARRAY[@]}
do
        echo $REMOVE | grep $str2 >/dev/null
        if [[ $? == 1 ]] #Not Found
        then
                RESULT="$RESULT $str2"
        fi
done

echo $RESULT

This is a bit verbose, uses BASH arrays, and is O(N*M), but works.

#!/bin/bash
REMOVE="package-x86 test0 hello world"
WORDBAG="computer hello sizeof compiler world package-x86 rocks test0"
OFS=$IFS
IFS=" "
REMOVE_ARRAY=($REMOVE)
WORDBAG_ARRAY=($WORDBAG)
IFS=$OFS
RESULT=""

for str2 in ${WORDBAG_ARRAY[@]}
do
        found=0
        for str1 in ${REMOVE_ARRAY[@]}
        do
                if [[ "$str1" == "$str2" ]]
                then
                        found=1
                fi
        done
        if [[ $found == 0 ]]
        then
                RESULT="$RESULT $str2"
        fi
done

echo $RESULT

Answer 3

How about any ugly abuse of the builtin command hash?

#!/bin/bash
set -eu

filter_out() {
    local words="$2" words_to_remove="$1"
    ( # do this in a subshell to avoid contaminating the main script
        set +e
        hash -r
        hash -p bogus-placeholder $words
        hash -d $words_to_remove > /dev/null 2>&1
        left=''
        for word in $words; do
            hash -t "$word" > /dev/null 2>&1 && left="${left}${left:+ }$word"
        done
        printf '%s\n' "$left"
    )
}

filter_out "package-x86 test0 hello world" "computer hello sizeof compiler world package-x86 rocks test0"
w='foo bar baz quux toto'
d='baz toto quux'
filter_out "$d" "$w"

Answer 4

#!/bin/bash
SET1="package-x86 test0 hello world"
SET2="computer hello sizeof compiler world package-x86 rocks test0"
awk -v s1="$SET1" -v s2="$SET2" 'BEGIN{
    m=split(s1,set1)
    n=split(s2,set2)
    for(i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            if ( set1[j] == set2[i]){
                 delete set2[i]
            }   
        }
    }
    for(i in set2) if (set2[i]!="") {print set2[i]}
}'

output

# ./shell.sh
compiler
rocks
computer
sizeof

Answer 5

This is, what, O(n) or O(n+m)?

#!/bin/bash
SET1="package-x86 test0 hello world"
SET2="computer hello sizeof compiler world package-x86 rocks test0"
for i in $SET2
do
    [[ ! $SET1 =~ $i  ]] && SET3="${SET3:+${SET3} }$i"
done
echo "..${SET3}.."

Running it:

$ ./script
..computer sizeof compiler rocks..

Answer 6

Without using anything bash-specific or external commands:

SET1="package-x86 test0 hello world"
SET2="computer hello sizeof compiler world package-x86 rocks test0"
SET3=

for arg in $SET2; do
  case $SET1 in
    $arg\ * | *\ $arg | *\ $arg\ *) ;;
    *) SET3="$SET3 $arg" ;;
  esac
done

Answer 7

It looks like you're looking for something with better than O(nm) running time, so here's an answer to that. Fgrep or grep -F uses the Aho-Corasick algorithm to make a single FSM out of a list of fixed strings, so checking each word in SET2 takes O(length of word) time. This means the whole running time of this script is O(n+m).

(obviously the running times are also dependent on the length of the words)

[meatmanek@yggdrasil ~]$ cat subtract.sh 
#!/bin/bash
subtract()
{
  SET1=( $1 )
  SET2=( $2 )
  OLDIFS="$IFS"
  IFS=$'\n'
  SET3=( $(grep -Fxv "${SET1[*]}" <<< "${SET2[*]}") )
  IFS="$OLDIFS"
  echo "${SET3[*]}"
  # SET3 = SET2-SET1
}
subtract "$@"
[meatmanek@yggdrasil ~]$ . subtract.sh 

[meatmanek@yggdrasil ~]$ subtract "package-x86 test0 hello world" "computer hello sizeof compiler world package-x86 rocks"
computer sizeof compiler rocks
[meatmanek@yggdrasil ~]$