find most frequently occurring letter/character combinations in a file

Question

find most frequently occurring letter/character combinations in a file

Instead of just looking for recurring words (a la: find n most frequent words in a file), I need to list all recurring letter combination strings...

Looking to record the most frequently occurring letter/character combinations of any/all length in a file?

Example list:

Stack
Exchange
Internet
Web
Question
Find
Frequent
Words
Combination
Letters
....

resulting repeating letter combinations:

[a,b,c,d,e,f,g,i,k,l,m,n,o,q,r,s,t,u,w,x]
in
ue
st
tion
ion
on
ti
et
te
ter
...

Ability to list results based on number of appearances = bonus :)

Answer 1

Any combination, assuming a minimum of two (for a minimum of N change {2,$l} to {N,$l}), ignoring case, per line, could be done via something like

% < examplelist 
Stack
Exchange
Internet
Web
Question
Find
Frequent
Words
Combination
Letters
% < examplelist perl -nlE '$_=lc; $l=length; next if $l < 2; m/(.{2,$l})(?{ $freq{$1}++ })^/; END { say "$freq{$_} $_" for keys %freq }' | sort -rg | head -4
3 in
2 ue
2 tion
2 tio

Answer 2

I need to list all recurring letter combination strings...

...so I made the script look at all possible lengths from 1 letter to complete line length (which is the word's length because the sample data feeds 1 word per line)...

The file ssf.mawk:

#!/usr/bin/mawk -f
BEGIN {
        FS=""
}
{
        _=tolower($0)
        for(i=1;i<=NF;i++)
                for(j=i;j<=NF;j++)
                        print substr(_,i,j-i+1) | "sort|uniq -c|sort -n"
}

Shortened output of a run with your sample input:

$ printf '%s\n' Stack Exchange Internet Web Question Find Frequent Words Combination Letters .... | ./ssf.mawk
      1 ....
      1 ac
      1 ack
      1 an
      1 ang

(((many lines omitted here)))

      4 s
      5 i
      8 n
      8 t
     10 e

I tested this with mawk-1.3.3 and gawk-4.1.1 on Debian8.

Answer 3

Here's a perl script that sorts output by occurrence. The minimum string length is configurable, and includes a debug option to see what's happening.

#!/usr/bin/perl
# Usage: perl script_file input_file

use strict;
my $min_str_len = 2;
my $debug = 0;

my %uniq_substrings;

while(<>)
{
    chomp;
    my $s = lc $_; # assign to $s for clearity

    printf STDERR qq|#- String: [%s]\n|, $s if $debug;
    my $line_len = length($s);
    for my $len ($min_str_len .. $line_len)
    {
        printf STDERR qq|# Length: %u\n|, $len if $debug;
        # break string into characters
        my @c  = split(//,$s);
        # iterate over list while large enough to provide strings of $len characters
        while(@c>=$len)
        {
            my $substring = join('', @c[0..$len-1]);
            my $curr_count = ++$uniq_substrings{$substring};
            printf STDERR qq|%s (%s)\n|, $substring, $curr_count if $debug;
            shift @c;
        }
    }
}

sub mysort
{
    # sort by count, subsort by alphabetic
    my $retval =
        ($uniq_substrings{$b} <=> $uniq_substrings{$a})
        || ($a cmp $b);
    return $retval;
}

for my $str (sort(mysort keys %uniq_substrings))
{
    printf qq|%s = %u\n|, $str, $uniq_substrings{$str};
}

Answer 4

Script:

MIN=2
MAX=5
while read A; do
    [ ${MAX} -lt ${#A} ] && max=${MAX} || max=${#A}
    for LEN in $(seq ${MIN} ${max}); do
        for k in $(seq 0 $((${#A}-${LEN}))); do
            echo "${A:$k:${LEN}}"
        done
    done
done <<< "$(cat file1|tr 'A-Z' 'a-z')" |sort|uniq -c|sort -k1,7rn -k9

With a bit of explanations:

# define minimal length of letters combinations
MIN=2
# define maximal length of letters combinations
MAX=5
# take line by line
while read A; do
    # determine max length of letters combination for this line
    # because it is shorter than MAX above if length of the line is shorter
    [ ${MAX} -lt ${#A} ] && max=${MAX} || max=${#A}
    # in cycle take one by one possible lengths of letters combination for line
    for LEN in $(seq ${MIN} ${max}); do
        # in cycle take all possible letters combination for length LEN for line
        for k in $(seq 0 $((${#A}-${LEN}))); do
            # print a letter combination
            echo "${A:$k:${LEN}}"
        done
    done
done <<< "$(cat file1|tr 'A-Z' 'a-z')" |sort|uniq -c|sort -k1,7rn -k9
# the data are taken from file "file1" and converted to lowercase,
# the data are sorted, unique lines counted,
# after results sorted according to string numerical values for numbers
# and strings with the same numbers sorted in alphabetical order

Output first 30 lines if parameters MIN=2 and MAX=5 (total output has 152 lines):

      3 in
      2 er
      2 et
      2 io
      2 ion
      2 nt
      2 on
      2 qu
      2 que
      2 st
      2 te
      2 ter
      2 ti
      2 tio
      2 tion
      2 ue
      1 ac
      1 ack
      1 an
      1 ang
      1 ange
      1 at
      1 ati
      1 atio
      1 ation
      1 bi
      1 bin
      1 bina
      1 binat
      1 ch
      ...

Output first 20 lines if parameters MIN=1 and MAX=3 (total output has 109 lines):

     10 e
      8 n
      8 t
      5 i
      4 o
      4 r
      4 s
      3 a
      3 c
      3 in
      2 b
      2 d
      2 er
      2 et
      2 f
      2 io
      2 ion
      2 nt
      2 on
      2 q
      ...