N-gram histogram

Question

Given a text and a number N, output, in a human readable format, the set of the character N-grams with their respective percentages.

The smallprint

• The text can be read from a file, stdin, passed as string parameter to a function or any other common way i forgot to mention
• The number N can be hardcoded, but only if it needs to be changed in one single place to change the functionality, the number counts as one byte regardless of the number of digits (T=input();N=100;f(T,N) would count as 20 bytes, not 22)
• No case sensitivity and all non-letter characters are treated the same. Inputs Abra Cadabra! and aBRa#caDAbrA5 should produce the same output. The character for non-letter can be any printable non-letter, not necessarily contained in the input
• You may assume N < text.length
• Output can be written to a file or displayed on screen. If you use a function you can return the result instead of printing as long as it is human readable (a JSON object or array like in the examples below is fine, a custom class or a sparse matrix with 27^N entries - not so much)

Examples with text = 'Abra Kadabra!'
N = 1

a 0.385
b 0.154
r 0.154
_ 0.154
k 0.076923
d 0.076923

N = 12

abra_kababra 0.5
bra_kadabra_ 0.5

N = 2 (dont worry about number format or rounding as long as it sums up to 0.99 < x < 1.01)

ab 0.1666666
br 0.16666
ra 0.1666
a. 0.166667
.k 0.0833333
ka 0.0833333
ad 8.33333e-2
da 0.0833333

a tree structure is fine too

{'a':{'b':0.166, '.':0.166, 'd': 0.0833},
 'b':{'r':0.166},
 'r':{'a':0.166}, 
 '.':{'k':0.0833}, 
 'k':{'a':0.0833}, 
 'd':{'a':0.0833}}

or a list of lists

[['A', 'B', 0.166], ['B', 'R', 0.166], ...]

Answer 1

Pyth, 40 35 27 character

KCm>m?k}kGNrz0dQ{m,bc/KblKK

Try it online: Pyth Compiler/Executor

For the input Abra Kadabra!, 2 it prints something like (the order is each time different, because of the behavior of set):

{(('d', 'a'), 0.08333333333333333), (('r', 'a'), 0.16666666666666666), (('b', 'r'), 0.16666666666666666), (('"', 'k'), 0.08333333333333333), (('a', 'b'), 0.16666666666666666), (('k', 'a'), 0.08333333333333333), (('a', '"'), 0.16666666666666666), (('a', 'd'), 0.08333333333333333)}

I use " as special character.

Explanation

m?k}kGNrz0         implicit: z = raw_input() # input_string
m      rz0         map each character k of z.lower() to:
  k   N                k                     '"'
 ? }kG                    if k in "a-z" else 
We call the result X. 

KCm>XdQ             implicit: Q = input() # number N
  m   Q             map each d in [0, 1, 2, ..., Q - 1] to:
   >Xd                  X[d:] # all characters of X starting at position d
 C                  zip - creates all N-grams
K                   store the results in variable K

{m,bc/KblKK
 m        K         map each b in K to:
  ,b                    the pair (b,                    )
     /Kb                             K.count(b)
    c   lK                                      / len(K)
{             set - remove duplicates

Printing in a 'human readable format': 35 character

KCm>m?k}kG\_rz0dQjbo_eN{m,sbc/KblKK

Try it online: Pyth Compiler/Executor

For the input: Abra Kadabra!, 2 it prints:

('a_', 0.16666666666666666)
('ab', 0.16666666666666666)
('ra', 0.16666666666666666)
('br', 0.16666666666666666)
('ka', 0.08333333333333333)
('da', 0.08333333333333333)
('_k', 0.08333333333333333)
('ad', 0.08333333333333333)

Explanation (differences)

\_ instead of N in m?k}kGNrz0
Uses '_' instead of '"'

s in {m,sbc/KblKK
This combines the individual characters

jbo_eN
  o                 order the elements N by:
   _eN                  the value -N[-1] (by the negative percentage)
jb                  join by newlines - prints each pair in row

Answer 2

J, 57 55 48 characters.

As a dyadic verb, N goes left, text goes right.

[:((a.{~97+~.);"#:#/.~%#)((u:97+i.26)i.tolower)\

Example

2 ([:((a.{~97+~.);"#:#/.~%#)((u:97+i.26)i.tolower)\) 'Abra Kadabra!'

yields:

┌──┬─────────┐
│ab│0.166667 │
├──┼─────────┤
│br│0.166667 │
├──┼─────────┤
│ra│0.166667 │
├──┼─────────┤
│a{│0.166667 │
├──┼─────────┤
│{k│0.0833333│
├──┼─────────┤
│ka│0.0833333│
├──┼─────────┤
│ad│0.0833333│
├──┼─────────┤
│da│0.0833333│
└──┴─────────┘

Thanks to randomra for a nine character improvement.

Explanation

This is the solution with spaces inserted in the appropriate places:

[: ((a. {~ 97 + ~.) ;"#: #/.~ % #) ((u: 97 + i. 26) i. tolower)\

First, observe that "#: is shorthand for "1 0 and that u: 97 + i. 26 is just 'abcdefghijklmnopqrstuvwxyz', so without these two tricks we get

[: ((a. {~ 97 + ~.) ;"1 0 #/.~ % #) ('abcdefghijklmnopqrstuvwxyz' i. tolower)\

And this is how this works. In the following explanation, x and y are the left and right arguments, u and v are verbs, and m and n are nouns.

1. [: u v—a capped fork, x ([: u v) y is equal to u (x v y). This is used instead of u@v because v is an adverbial phrase and parentheses were needed. In this code, u is (a. {~ 97 + ~.) ;"#: #/.~ % # and v is ((u: 97 + i. 26) i. tolower)\.

2. x u\ y—apply u to each infix of y of length x. For example, 3 ]\ 'abcdefg' where ] is the identity function yields

   abc
   bcd
   cde
   def
   efg
   

3. n u v—a fork with a noun as the left argument. (n u v) y is equal to n u (v y). This is used multiple times in the code.

4. tolower y–convert all upper case letters in y to lower case.

5. x i. y–find the index of y, which is in this case for each item in y the lowest index into x at which that item can be found or the number of items in x if such an item does not exist. In our use case, x is the lower case alphabet. ('abcdefghijklmnopqrstuvwxyz' i. tolower) y translated each (upper case or lower case) letter in y into a number from 0 to 25. Non-letters are translated into 26. Notice that the character immediately following z in ASCII is {.

6. x u/. y–applies u to y keyed by x. That is, u is applied to groups of items of y with the same key in x. Noticeably, if x and y are equal, y u/. y applies u to groups of equal items of y and can be used to generate frequency statistics.

7. # y–the tally of y, that is, the number of items in y.

8. u~–the reflexive of u, that is, u~ y is equal to y u y.

9. u v w–a fork, (u v w) y is equal to (u y) v (w y). This, too, is used multiple times in the code.

10. x % y–x divided by y.

11. #/.~ % #–the frequency count we want sans what we count.

12. ~. y–the nub of y, that is, each distinct item of y. For instance, ~. 1 2 3 3 4 6 6 6 yields 1 2 3 4 6.

13. (a. {~ 97 + ~.) y–the nub of y converted from indices into the alphabet back to letters; 26 is converted into { implicitly.

14. x ; y–x linked to y, that is, both put into boxes and the boxes concatenated. For instance, 'abc' ; 1 2 3 4 yields

    ┌───┬───────┐
    │abc│1 2 3 4│
    └───┴───────┘
    

    This is needed because in J, arrays are homogeneous; all items in an array need to have same type. A box hides what is in it and turns heterogeneous arrays into arrays of boxes.

15. u"n–u ranked n. Rank is a slightly complex concept so I won't explain it here, but in this case, x ;"1 0 y (for which x ;"#: y is just a shorthand) applies ; to each string in x and the corresponding number in y as opposed to the entire of x and the entire of y. This is the difference between

    ┌──┬───────────────────────────────────────────────────────────────────────────┐
    │ab│0.166667 0.166667 0.166667 0.166667 0.0833333 0.0833333 0.0833333 0.0833333│
    │br│                                                                           │
    │ra│                                                                           │
    │a{│                                                                           │
    │{k│                                                                           │
    │ka│                                                                           │
    │ad│                                                                           │
    │da│                                                                           │
    └──┴───────────────────────────────────────────────────────────────────────────┘
    

    and the correct output shown above.

Answer 3

CJam, 53 bytes

q~el_'{,97>-'_er_,,\f>1$(W*<f<:L__&_@f{\a/,(}L,df/]z`

Without having a look at the other CJam answer, here is a shorter one.

Input goes like:

2 "Abra Kadabra!"

Output is like:

[["ab" 0.16666666666666666] ["br" 0.16666666666666666] ["ra" 0.16666666666666666] ["a_" 0.16666666666666666] ["_k" 0.08333333333333333] ["ka" 0.08333333333333333] ["ad" 0.08333333333333333] ["da" 0.08333333333333333]]

Explanation soon.

Try it online here

Answer 4

BQN, 56 bytes

"A[a{"⊸⍋⊸({2|𝕨?𝕩+16׬𝕨;'_'}¨)⊸{u⋈˘(≠s)÷˜+´˘⍷⟜𝕨˘u←⍷s←𝕩↕𝕨}

Anonymous function that takes a string on the left and the number N on the right. It returns a 2-D array, in which each row contains a length-N substring and a 0-D array containing the substring's frequency. Try it at BQN online!

Explanation

Wow this is ugly--and not just because of BQN's total lack of character/string primitives.

The first half normalizes the string argument by converting lowercase letters to uppercase and non-letters to underscores:

"A[a{"⊸⍋⊸({2|𝕨?𝕩+16׬𝕨;'_'}¨)
"A[a{"⊸⍋                        Classify the characters: 0 if < 'A', 1 if >= A but
                                 < '[', and so forth (meaning, in particular, 1 for
                                 uppercase letters and 3 for lowercase letters)
        ⊸(                   )  With that as the left argument and the original
                                string as the right argument,
          {                }¨   call this function on each number-character pair:
           2|𝕨?                  If the number is odd (1 or 3):
                    ¬𝕨            1 minus the number
                 16×              times 16
               𝕩+                 plus the character
                       ;'_'      Else, underscore

Now the actual meat of the function:

⊸{u⋈˘(≠s)÷˜+´˘⍷⟜𝕨˘u←⍷s←𝕩↕𝕨}
⊸{                          }  Pass the left argument through the above function
                               before calling this function:
                        𝕩↕𝕨    Get all length-(right arg) substrings of (left arg)
                      s←       Save that 2D array of characters as s
                     ⍷         Deduplicate
                   u←          Save that 2D array of characters as u
              ⍷⟜𝕨˘            For each row of u, find all occurrences of that
                               substring in the left arg; mark the beginning of
                               an occurrence with a 1, all other positions with a 0
           +´˘                 Sum each row, giving a list of occurrence counts
         ÷˜                    Divide each by
     (≠s)                      the length of s
   ⋈˘                          Pair each with
  u                            the corresponding unique substring

Answer 5

CJam, 61 59 bytes

I think the input transformation is quite nifty, but the actual tallying needs work.

l~qeu'~),_el&'_er_,,2$f{2$@><\}\W*<:L__&\f{1$a/,(L,d/][};]`

Reads N on the first line and then treats the remainder of STDIN as the text:

2
Abra Kadabra!

The result is printed as a nested CJam-style array with upper case letters and _ for non-letters:

[["AB" 0.16666666666666666] ["BR" 0.16666666666666666] ["RA" 0.16666666666666666] ["A_" 0.16666666666666666] ["_K" 0.08333333333333333] ["KA" 0.08333333333333333] ["AD" 0.08333333333333333] ["DA" 0.08333333333333333]]

Test it here.

Answer 6

Haskell, 164 bytes

import Data.Char
import Data.List
l=genericLength
c c|isAlpha c=toLower c|1<2='_'
n%i=[(s!!0,l s/l p)|s<-group p]where p=sort[take n s|s<-tails$map c i,length s>=n]

Usage: 12 % "Abra Kadabra!" -> [("abra_kadabra",0.5),("bra_kadabra_",0.5)]

This is longer than I thought. Does anyone know a shorter version of a "split list into sublists of length n" function (my attempt: [take n s|s<-tails$ i,length s>=n])?

How it works:

• map all characters in the input list to lowercase or '_' if not a letter
• split into a list of substrings of length n
• sort, name the list p
• group equal elements (e.g. for n=2 -> [["_k"],["a_","a_"],["ab","ab"],["ad"],["br","br"],["da"],["ka"],["ra","ra"]]
• for each sublist take one of it's elements and pair it with the length divided by the length of p

Answer 7

Clip 10, 53

\[tm[b{(b/)b)mlxt`}q[bm[juj+jtb}R)mlbt]a[!cA}m.U`xS]n

Example:

C:\Users\~~~~~\Documents>java -jar Clip10.jar ngram.clip
Abra Kadabra!
2
{{"AB", 0.166666666666666}, {"A ", 0.166666666666666}, {"RA", 0.166666666666666}, {"BR", 0.166666666666666}, {"DA", 0.083333333333333}, {" K", 0.083333333333333}, {"KA", 0.083333333333333}, {"AD", 0.083333333333333}}

Explanation

 [t                                               ]n .- Assign the second input to t -.
                                            m.U`x    .- Convert the input to upper case -.
                                      a[!cA}     S   .- Replace all non-alphabetic characters with spaces -.
                   [b                ]               .- Assign the modified string to b -.
                     m[juj+jtb}R)mlbt                .- All substrings of length t -.
                  q                                  .- Frequencies (in the form {"A", 1} )-.
   m[b{(b/)bmlxt`}                                   .- Use proportional frequencies
\                                                    .- Make the array pretty -.

Answer 8

Mathematica, 124 119 bytes

Could probably golf further.

#[[1]]->#[[2]]&/@#/Length@#&@Tally@Partition[Characters@StringReplace[ToLowerCase@#,Except@LetterCharacter->"_"],#2,1]&

Answer 9

APL (Dyalog Classic) with MiServer's Strings.lc, 30 bytes

Prompts for text, then for N. Prints N-grams and frequencies.

(∪,⊢∘≢⎕U2338÷≢)⎕,/'\W'⎕R'_'lc⍞

Try it online!

Only 25 characters (but 44 bytes) in Dyalog Unicode:

(∪,⊢∘≢⌸÷≢)⎕,/'\W'⎕R'_'lc⍞

… because ⌸ ⇔ ⎕U2338, but is not included in the Classic character set.

Explanation

⍞ get text input

lc lowercase

'\W'⎕R'_' PCRE Replace non-word characters with underscores

,/ concatenate the characters in each possible position of a sliding window of size

⎕ number-input

(…) apply the following anonymous tacit function on that (the N-grams):

 ∪ the unique (N-grams)

 , followed by

 ⊢∘≢⌸ the number occurrences for each unique element (of the N-grams)

 ÷ divided by

 ≢ the tally (of N-grams)

Answer 10

Ruby, 86 bytes

->s,n{s.upcase.gsub(/[^A-Z]/,?_).chars.each_cons(n).tally.map{[_1,_2/(s.size-n+1.0)]}}

Attempt This Online!

Answer 11

Python, 92 bytes

lambda s,k:(b:=1+len(s)-k)//b*(a:=[s[i:i+k]for i in range(b)])and{t:a.count(t)/b for t in a}

Attempt This Online!

Answer 12

05AB1E, 24 bytes

„üÿUáмS¡'_ýlDX.VÙDŠ¢DO/ø

Inputs in the order N, text. Outputs as a list of [string, decimal] pairs. A trailing » (+1 byte) could be added to pretty-print them to STDOUT.

Try it online or verify all test cases.

Explanation:

„üÿ       # Push string "üÿ", where `ÿ` is automatically replaced with the first
          # (implicit) input-integer
   U      # Pop and store this string in variable `X`
á         # Only keep all letters of the second (implicit) input-string
 м        # Remove all those letters from the second (implicit) input-string
  S       # Convert the remaining string of characters to a list
   ¡      # Split the second (implicit) input-string on those characters
    '_ý  '# Join it with "_" delimiter
       l  # Convert this string to lowercase
D         # Duplicate the string
 X        # Push string `X` we created earlier
  .V      # Evaluate and execute it as 05AB1E code,
          # creating overlapping substrings of size `N`
    Ù     # Uniquify this list
D         # Duplicate the unique substrings
 Š        # Triple-swap from a,b,b to b,a,b
  ¢       # Pop the string and list, and count how many times each string occurs
   D      # Duplicate the list of counts
    O     # Sum it together
     /    # Divide the individual counts by the sum
      ø   # And pair it with the substrings we've duplicated
»         # (Optional) join each pair by spaces, and then each string by newlines
          # (after which the result is output implicitly)