Generate ngrams with Julia

Question

To generate word bigrams in Julia, I could simply zip through the original list and a list that drops the first element, e.g.:

julia> s = split("the lazy fox jumps over the brown dog")
8-element Array{SubString{String},1}:
 "the"  
 "lazy" 
 "fox"  
 "jumps"
 "over" 
 "the"  
 "brown"
 "dog"  

julia> collect(zip(s, drop(s,1)))
7-element Array{Tuple{SubString{String},SubString{String}},1}:
 ("the","lazy")  
 ("lazy","fox")  
 ("fox","jumps") 
 ("jumps","over")
 ("over","the")  
 ("the","brown") 
 ("brown","dog") 

To generate a trigram I could use the same collect(zip(...)) idiom to get:

julia> collect(zip(s, drop(s,1), drop(s,2)))
6-element Array{Tuple{SubString{String},SubString{String},SubString{String}},1}:
 ("the","lazy","fox")  
 ("lazy","fox","jumps")
 ("fox","jumps","over")
 ("jumps","over","the")
 ("over","the","brown")
 ("the","brown","dog") 

But I have to manually add in the 3rd list to zip through, is there an idiomatic way such that I can do any order of n-gram?

e.g. I'll like to avoid doing this to extract 5-gram:

julia> collect(zip(s, drop(s,1), drop(s,2), drop(s,3), drop(s,4)))
4-element Array{Tuple{SubString{String},SubString{String},SubString{String},SubString{String},SubString{String}},1}:
 ("the","lazy","fox","jumps","over") 
 ("lazy","fox","jumps","over","the") 
 ("fox","jumps","over","the","brown")
 ("jumps","over","the","brown","dog")

Hydrotherapy

Answer 1

Here's a clean one-liner for n-grams of any length.

ngram(s, n) = collect(zip((drop(s, k) for k = 0:n-1)...))

It uses a generator comprehension to iterate over the number of elements, k, to drop. Then, using the splat (...) operator, it unpacks the Drops into zip, and finally collects the Zip into an Array.

julia> ngram(s, 2)
7-element Array{Tuple{SubString{String},SubString{String}},1}:
 ("the","lazy")  
 ("lazy","fox")  
 ("fox","jumps") 
 ("jumps","over")
 ("over","the")  
 ("the","brown") 
 ("brown","dog") 

julia> ngram(s, 5)
4-element Array{Tuple{SubString{String},SubString{String},SubString{String},SubString{String},SubString{String}},1}:
 ("the","lazy","fox","jumps","over") 
 ("lazy","fox","jumps","over","the") 
 ("fox","jumps","over","the","brown")
 ("jumps","over","the","brown","dog")

As you can see, this is very similar to your solution - only a simple comprehension was added to iterate over the number of elements to drop, so that the length could be dynamic.

Nerty

Oh cool! Thanks @HarrisonGrodin, didn't know that drop(s,0) is possible =) – Hydrotherapy

@Hydrotherapy No problem! Also, in the case that drop(s,0) was not possible, the following would work. :) zip(s, (drop(s,k) for k=1:n-1)...) – Nerty

Answer 2

By changing the output slightly and using SubArrays instead of Tuples, little is lost, but it is possible to avoid allocations and memory copying. If the underlying word list is static, this is OK and faster (in my benchmarks too). The code:

ngram(s,n) = [view(s,i:i+n-1) for i=1:length(s)-n+1]

and the output:

julia> ngram(s,5)
 SubString{String}["the","lazy","fox","jumps","over"] 
 SubString{String}["lazy","fox","jumps","over","the"] 
 SubString{String}["fox","jumps","over","the","brown"]
 SubString{String}["jumps","over","the","brown","dog"]

julia> ngram(s,5)[1][3]
"fox"

For larger word lists the memory requirements are substantially smaller also.

Also note using a generator allows processing the ngrams one-by-one faster and with less memory and might be enough for the desired processing code (counting something or passing through some hash). For example, using @Gnimuc's solution without the collect i.e. just partition(s, n, 1).

Veneaux

Answer 3

Another way is to use Iterators.jl's partition():

ngram(s,n) = collect(partition(s, n, 1))

Githens

Julia 1.8 now implements eachsplit, so you will be able to define ngram(s::S, n) where {S <: AbstractString} = partition(eachsplit(s), n), which will return an iterator. – Skyla