[SOLVED] SED with back-references

This is a learning exercise.

Have: a large file of English words, one word on each line.

Want: a subset of the file where all words
meet these criteria ...
(1) have 6 letters
(2) letters 1 and 3 are the same
(3) no letters are repeated other than 1 and 3

This sed ...

sed -nr "/^(.)(.)\1([^\1\2])([^\1\2\4])([^\1\2\4\5])$/p"  \
<$WordList >$OutFile

.. produces a file which contains words such as ...

abacus
alarms
amazon
analog
apathy

... which fit the criteria ...

... but also contains words such as ...

avatar
acacia
bubble
cicada
cyclic

... which do not fit criterion #3.

Please advise.

Daniel B. Martin

.

You can't put a backreference inside a character class, so "[^\1\2]" doesn't match what you think it does - it is simplified to "[^12]" which is why the criteria is effectively ignored (if any of your words had those digits as fourth character they would be excluded).

What you're trying to achieve can be done with negative lookaheads, but Sed's regex does not support this (not even in extended mode) - you'd need to use Perl/Python/Java/etc for that method.

There might be a different way to conditionally check the backreferences with Sed, but - if I couldn't do it with regex in Perl/etc - I suspect Awk (with each letter a field) would provide a clearer solution.

Somehow, I feel a sense of déjà vu.

Originally Posted by danielbmartin (3) no letters are repeated other than 1 and 3

1. I do not think it is possible using sed, but I'm not really sure about that.
2. if there was any solution in sed, that would be extremely complicated - and most probably requires more than one single step.
3. but you can easily implement a function in perl/python/java/whatever which can check if that condition [above] is really fulfilled (not a oneliner).

Does this meet you criteria?

egrep -x '(.).\1...' /usr/share/dict/words|egrep -v '(.).*\1.?.?$'

The sed equivalent would be

sed -En '/^(.).\1...$/{/(.).*\1.?.?$/!p}' /usr/share/dict/words

or

sed -r '/^(.).\1...$/!d;/(.).*\1.?.?$/d' /usr/share/dict/words

Originally Posted by shruggy Does this meet you criteria? egrep -x '(.).\1...' /usr/share/dict/words|egrep -v '(.).*\1.?.?$' The sed equivalent would be sed -En '/^(.).\1...$/{/(.).*\1.?.?$/!p}' /usr/share/dict/words

no, that sed could not check if the first and second chars are the same.

grep -Ev '..*?(.).*\1' a.txt| grep -E '^(.).\1'

You are right, of course. Fortunately, there are no six-letter words in the dictionary that start with three identical letters:

[color=]$ [/color]egrep '^(.)\1\1' /usr/share/dict/words
AAA
aaa
AAAA
AAAAAA
AAAL
AAAS
BBB
CCC
CCCCM
CCCI
DDD
EEE
iii
KKK
MMM
mmmm
oooo
PPP
SSS
TTTN
xxx
ZZZ

Nevertheless, the corrected sed expression:

 sed -r '/^(.).\1...$/!d;/^(.)\1|(.).*\2.?.?$/d' /usr/share/dict/words

^^^ impressive...

Originally Posted by shruggy Nevertheless, the corrected sed expression: sed -r '/^(.).\1...$/!d;/^(.)\1|(.).*\2.?.?$/d' /usr/share/dict/words

yes, nice, looks similar to the grep I posted. Also solves the problem: sed cannot handle greediness (of regexp).

Originally Posted by pan64 sed cannot handle greediness (of regexp).

Neither can grep -E:

$ echo abab|grep -Eo '^.*?b'
abab
$ echo abab|grep -Po '^.*?b'
ab

Originally Posted by shruggy Neither can grep -E: $ echo abab|grep -Eo '^.*?b' abab $ echo abab|grep -Po '^.*?b' ab

Yes, that's why was this problem so hard. Fortunately there was a way...

I mean your solution doesn't require lazy quantifiers either (with string length limited to only six characters by the first regex, backtracking in the second one is not much of an issue):

sed -r '/^(.).\1...$/!d;/.+(.).*\1/d' /usr/share/dict/words