How does awk '!a[$0]++' work?

Question

This one-liner removes duplicate lines from text input without pre-sorting.

For example:

$ cat >f
q
w
e
w
r
$ awk '!a[$0]++' <f
q
w
e
r
$ 

The original code I have found on the internets read:

awk '!_[$0]++'

This was even more perplexing to me as I took _ to have a special meaning in awk, like in Perl, but it turned out to be just a name of an array.

Now, I understand the logic behind the one-liner: each input line is used as a key in a hash array, thus, upon completion, the hash contains unique lines in the order of arrival.

What I would like to learn is how exactly this notation is interpreted by awk. E.g. what the bang sign (!) means and the other elements of this code snippet.

How does it work?

Answer 1

Here is a "intuitive" answer, for a more in depth explanation of awk's mechanism see either @Cuonglm's

In this case, !a[$0]++, the post-increment ++ can be set aside for a moment, it does not change the value of the expression. So, look at only !a[$0]. Here:

a[$0]

uses the current line $0 as key to the array a, taking the value stored there. If this particular key was never referenced before, a[$0] evaluates to the empty string.

!a[$0]

The ! negates the value from before. If it was empty or zero (false), we now have a true result. If it was non-zero (true), we have a false result. If the whole expression evaluated to true, meaning that a[$0] was not set to begin with, the whole line is printed as the default action.

Also, regardless of the old value, the post-increment operator adds one to a[$0], so the next time the same value in the array is accessed, it will be positive and the whole condition will fail.

Answer 2

Here is the processing:

• a[$0]: look at the value of key $0, in associative array a. If it does not exist, automatically create it with an empty string.

• a[$0]++: increment the value of a[$0], return the old value as value of expression. The ++ operator returns a numeric value, so if a[$0] was empty to begin with, 0 is returned and a[$0] incremented to 1.

• !a[$0]++: negate the value of expression. If a[$0]++ returned 0 (a false value), the whole expression evaluates to true, and makes awk perform the default action print $0. Otherwise, if the whole expression evaluates to false, no further action is taken.

References:

• Expression in awk
• gawk - Increment and Decrement Operators

With gawk, we can use dgawk (or awk --debug with newer version) to debug a gawk script. First, create a gawk script, named test.awk:

BEGIN {                                                                         
    a = 0;                                                                      
    !a++;                                                                       
}

Then run:

dgawk -f test.awk

or:

gawk --debug -f test.awk

In debugger console:

$ dgawk -f test.awk
dgawk> trace on
dgawk> watch a
Watchpoint 1: a
dgawk> run
Starting program: 
[     1:0x7fe59154cfe0] Op_rule             : [in_rule = BEGIN] [source_file = test.awk]
[     2:0x7fe59154bf80] Op_push_i           : 0 [PERM|NUMCUR|NUMBER]
[     2:0x7fe59154bf20] Op_store_var        : a [do_reference = FALSE]
[     3:0x7fe59154bf60] Op_push_lhs         : a [do_reference = TRUE]
Stopping in BEGIN ...
Watchpoint 1: a
  Old value: untyped variable
  New value: 0
main() at `test.awk':3
3           !a++;
dgawk> step
[     3:0x7fe59154bfc0] Op_postincrement    : 
[     3:0x7fe59154bf40] Op_not              : 
Watchpoint 1: a
  Old value: 0
  New value: 1
main() at `test.awk':3
3           !a++;
dgawk>

You can see, Op_postincrement was executed before Op_not.

You can also use si or stepi instead of s or step to see more clearly:

dgawk> si
[     3:0x7ff061ac1fc0] Op_postincrement    : 
3           !a++;
dgawk> si
[     3:0x7ff061ac1f40] Op_not              : 
Watchpoint 1: a
  Old value: 0
  New value: 1
main() at `test.awk':3
3           !a++;

Answer 3

ah the ubiquitous but also ominous awk duplicate remover

awk '!a[$0]++'

this sweet baby is the love child of awk's power and terseness. the pinacle of awk one liners. short but powerful and arcane all at once. removes duplicates while maintaining order. a feat unachieved by uniq or sort -u which removes only adjacent duplicates or has to break order to remove duplicates. (although is does so at the cost of memory consumption.)

here is my attempt to explain how this awk one liner works. i took effort in explaining things so that someone who does not know any awk can still follow along. i hope i was able to do so.

first some background: awk is a programming language. this command awk '!a[$0]++' invokes the awk interpreter/compiler on the awk code !a[$0]++. similar to python -c 'print("foo")' or node -e 'console.log("foo")'. awk code are often one liners because awk was specifically designed to be concise for quick text filtering on the command line.

now some pseudo code. what this one liner does is basically the following:

for every line of input
  if i have not seen this line before then
    print line
  take note that i have now seen this line

i hope you can see how this removes duplicates while maintaining order. (also how it does so at the cost of memory consumption.)

but how does a loop, an if, a print, and a mechanism for storing and retrieving strings fit in 8 characters of awk code? the answer is implicit.

the loop, the if, and the print is implicit.

to explain let us again examine some pseudo code:

for every line of input
  if line matches some condition then
    execute some code on line

this is a typical filter which you probably have written a lot in some form or another in your code in any language. the awk language is designed so that writing these kinds of filter is super short.

awk does the loop for us and skips the boilerplate for the if. so we just need to write the condition and the code in the if block:

condition { code block }

in awk this is called a "rule".

we can omit either the condition or the code block (obviously we cannot omit both) and awk will fill the mising part with some implicits.

if we omit the condition

{ code block }

then it will be implicit true

true { code block }

which means code block will be executed for every line

if we omit the code block

condition

then it will be implicit print current line

condition { print current line }

let's look at our original awk code again

!a[$0]++

it does not sit inside curly braces so it is the conditional part of a rule.

let's write out the implicit loop and if and print

for every line of input
  if !a[$0]++ then
    print line

compare to our original pseudo code

for every line of input                      # implicit by awk
  if i have not seen this line before then   # at least we know the conditional part
    print line                               # implicit by awk
  take note that i have now seen this line   # ???

we understand the loop, the if, and the print. but how does it work so that it evaluates to false only at duplicate lines? and how does it take note of lines already seen?

let's take apart this beast:

!a[$0]++

if you know some c or java you should already know some of the symbols. the semantics are identical or at least similar.

the exclamation mark (!) is a negator. it evaluates the expression to a boolean and whatever the result it is negated. if the expression evaluates to true the end result is false and vice versa.

a[..] is an array. an associative array. other languages name it map or dictionary. in awk all arrays are associative arrays. the a has no special meaning. it is just a name for the array. it could just as well be x or eliminatetheduplicate.

$0 is the current line from the input. this is an awk specific variable.

the plus plus (++) is a post increment operator. this operator is a bit tricky because it does two things: the value in the variable is incremented. but it also "returns" the original, not incremented, value for further processing.

   !        a[         $0       ]        ++
negator   array   current line      post increment

how do they work together?

roughly in this order:

1. $0 is the current line
2. a[$0] is the value in the array for the current line
3. the post increment (++) gets the value from a[$0]; increments and stores it back to a[$0]; then "returns" the original value to the next operator in line: the negator.
4. the negator (!) gets a value from the ++ which was the original value from a[$0]; it is evaluated to a boolean then negated then passed to the implicit if.
5. the if then decides whether to print the line or not.

so that means whether the line gets printed or not, or in the context of this awk program: whether the line is a duplicate or not, is ultimately decided by the value in a[$0].

by extension: the mechanism that is taking note whether this line has already been seen must then happen when ++ stores the incremented value back to a[$0].

let's look at our pseudo code again

for every line of input
  if i have not seen this line before then   # decided based on value in a[$0]
    print line
  take note that i have now seen this line   # happens by increment from ++

some of you might already see how this plays out but we have gone this far let us take the last few steps and take appart the ++

we start with the awk code embedded in the implicits

for each line as $0
  if !a[$0]++ then
    print $0

let's introduce variables to have some room to work

for each line as $0
  tmp = a[$0]++
  if !tmp then
    print $0

now we take the ++ apart.

remember that this operator does two things: increment the value in the variable and return the original value for further processing. so the ++ becomes two lines:

for each line as $0
  tmp = a[$0]       # get original value
  a[$0] = tmp + 1   # increment value in variable
  if !tmp then      # decide based on original value
    print $0

or in other words

for each line as $0
  tmp = a[$0]       # query if have seen this line
  a[$0] = tmp + 1   # take note that has seen this line
  if !tmp then      # decide based on query
    print $0

compare to our first pseudo code

for every line of input:
  if i have not seen this line before:
    print line
  take note that i have now seen this line

so there we have it. we have the loop, the if, the print, the query and the note taking. just in a different order than the pseudo code.

condensed to 8 characters

!a[$0]++

possible because of awks implicit loop, implicit if, implicit print, and because the ++ does both the query and note taking.

remains one question. what is the value of a[$0] for the first line? or for any line that has not been seen before? the answer is again implicit.

in awk any variable that is used for the first time is implicitly declared and initialized to an empty string. except arrays. arrays are declared and initialized to an empty array.

the ++ does implicit conversions to number. the empty string converts to zero. other strings will be converted to a number by some best effort algorithm. if the string is not recognized as a number it again converts to zero.

the ! does implicit conversion to boolean. the number zero and the empty string converts to false. anything else converts to true.

that means when a line is seen for the first time then a[$0] is set to the empty string. the empty string is converted to zero by ++ then incremented to 1 and stored back in a[$0]. the original zero is converted to false by !. the result from ! is true so the line gets printed.

the value in a[$0] is now the number 1.

if a line is seen the second time then a[$0] is the number 1 which converts to true and the result from ! is false so it is not printed.

any further encounter of the same line increases the number. since all numbers except zero are true the result from ! will always be false so the line never gets printed again.

that is how the duplicates are removed.

TL;DR: it counts how often a line has been seen. if zero then print. if any other number then no print. it can be short because of many implicits.

---

bonus: some variants of the one liner and super short explanation of what it does.

replace $0 (entire line) with $2 (second column) will remove duplicates but only based on the second column

$ cat input 
x y z
p q r
a y b

$ awk '!a[$2]++' input 
x y z
p q r

replace ! (negator) with ==1 (equal to one) and it will print the first line that is a duplicate

$ cat input 
a
b
c
c
b
b

$ awk 'a[$0]++==1' input 
c
b

replace with >0 (greater than zero) and add {print NR":"$0} will print all duplicate lines with line number. NR is a special awk variable containing the line number (record number in awk lingo).

$ awk 'a[$0]++>0 {print NR":"$0}' input 
4:c
5:b
6:b

i hope these examples help to further grasp the concepts explained above.

Answer 4

Just want to add that both expr++ and ++expr are just a shorthand for expr=expr+1. But

$ awk '!a[$0]++' f # or 
$ awk '!(a[$0]++)' f

will print all unique values since expr++ will evaluate to expr before the addition, while

$ awk '!(++a[$0])' f

will just print nothing since ++expr will evaluate to expr+1, which always return non-zero value in this case, and the negation will return zero value always.