how to count number of distinct/unique words in a string variable?

[Mariano Mastrogiorgio]

Hello,

I have a dataset like this one:

idvar stringvar
1 'word x','word y',...
2 'word z', 'word z', 'word z',...
3 ...

I need a new variable that counts the number of distinct/unique items in stringvar for each observation. Basically, I need to count the number of unique/distinct words, with no repetitions, for each observation. I know that the solutions may be very easy, but I have been struggling with it the whole day. Words are delimited by ' ' and separated by ,. I need a simple one-line solutions. I have been trying more complex approaches, like splitting stringvar into separate words, but it is too complex due to the huge size of my database.

Thank you
M.

[Nick Cox]

SJ-9-1  pr0046  . . . . . . . . . . . . . . . . . . .  Speaking Stata: Rowwise
        (help rowsort, rowranks if installed) . . . . . . . . . . .  N. J. Cox
        Q1/09   SJ 9(1):137--157
        shows how to exploit functions, egen functions, and Mata
        for working rowwise; rowsort and rowranks are introduced

discussed essentially this problem, following which an egen function rowsvals() was added to egenmore on SSC.

Here is the main idea.

clear
input str21 strvar
"frog"
"frog frog"
"frog toad frog"
"frog toad newt dragon"
end

split strvar

egen ndistinct = rowsvals(strvar?)

list

     +--------------------------------------------------------------------------+
     |                strvar   strvar1   strvar2   strvar3   strvar4   ndisti~t |
     |--------------------------------------------------------------------------|
  1. |                  frog      frog                                        1 |
  2. |             frog frog      frog      frog                              1 |
  3. |        frog toad frog      frog      toad      frog                    2 |
  4. | frog toad newt dragon      frog      toad      newt    dragon          4 |
     +--------------------------------------------------------------------------+

[Clyde Schechter]

I don't think there is any possible one-line solution to this. The shortest I could come up with is five lines. And it's not particularly complicated.

* Example generated by -dataex-. For more info, type help dataex
clear
input byte idvar str50 stringvar
1 "apple, peach, banana, cherry"                      
2 "apple, apple, peach, peach"                        
3 "apple, cherry, apple, banana"                      
4 "apple, peach, banana, cherry, cherry, dragon fruit"
end

split stringvar, parse(", ") gen(word)
reshape long word, i(idvar)
by idvar (word), sort: gen distinct_count = sum(word != word[_n-1])
by idvar: replace distinct_count = distinct_count[_N]
reshape wide

In the future, when showing data examples, please use the -dataex- command to do so, as I have here. If you are running version 18, 17, 16 or a fully updated version 15.1 or 14.2, -dataex- is already part of your official Stata installation. If not, run -ssc install dataex- to get it. Either way, run -help dataex- to read the simple instructions for using it. -dataex- will save you time; it is easier and quicker than typing out tables. It includes complete information about aspects of the data that are often critical to answering your question but cannot be seen from tabular displays or screenshots. It also makes it possible for those who want to help you to create a faithful representation of your example to try out their code, which in turn makes it more likely that their answer will actually work in your data.

Added: Crossed with #2. I was not aware of the -egen, rowsvals()- function. Nick's solution is simpler.

[Bjarte Aagnes]

Alternative not using split

gen strvar = orgvar // if keeping orgvar
replace strvar = subinstr(strvar, "'", "", .) // for example data
replace strvar = subinstr(strvar, ",", "", .) // for example data
replace strvar = ustrtrim(itrim(strvar))

gen wordcount = wordcount(strvar)
su  wordcount, meanonly
local wordcount = r(max)
drop wordcount

qui forvalues i = 1/`wordcount'  {
    
   replace strvar = subinword(strvar, word(strvar,1), "", .)  + char(32) + word(strvar,1)       
}

gen nwords = wordcount(strvar)

[Mariano Mastrogiorgio]

Hello,

thank you very much for the quick replies.

-I had already tried the split approach (thank you Nick and Clyde) on a small sample and it works, but unfortunately it does not work on my database due to its size. I am working with almost 2million observations and some word lists to split contain tens (even hundreds) of words, implying the creation of a high number of variables. Stata runs for hours without ending, when it does not crashes.

--> Any tip on how to make the process more efficient computationally? For example, without storing variables or similar approaches.

-Aagnes' approach seems promising. I am now trying it on the database, and it seems faster (but still running). I tried it on the small sample, it does count, but the count is not exact (I want the number of distinct/unique words), perhaps due to other elements in the string ('' or , or spaces). See the example below.

-->Any tip on how to fine tune the code?

'disease', 'disease', 'disease', 'disease', 'disease', 'disease', 'cardiovascular disease', 'cardiovascular disease', 'cardiovascular disease', 'cardiovascular disease', 'cardiovascular disease', 'cardiovascular disease', 'cardiovascular disease', 'chagas', 'chagas', 'infectious disease', 'infectious disease', 'infectious disease', 'infectious disease', 'infectious disease', 'infectious disease', 'infectious disease', 'infectious disease', 'infectious disease', 'infectious disease', 'infectious disease',


Thank you!

[Clyde Schechter]

So with millions of observations and hundreds of words per observation, yes, that is going to take a very long time, if it even runs at all--memory constraints will probably kill it.

But you can get around this easily because for this problem, each observation can be processed independently of all the others. So instead of doing all 2,000,000 observations together, break it into manageable size batches, do them separately, and put the results together. That may sound like a lot of work, but the -runby- command, written by Robert Picard and me, available from SSC, automates that process. You have to wrap the code for the problem-solving in a program to use it. Like this:

capture program drop one_batch
program define one_batch
    split stringvar, parse(", ") gen(word)
    reshape long word, i(idvar)
    by idvar (word), sort: gen distinct_count = sum(word != word[_n-1])
    by idvar: replace distinct_count = distinct_count[_N]
    reshape wide
    drop word*
    exit
end

local n_batches 1000
gen int batch = floor(idvar/`n_batches')
runby one_batch, by(batch) status

For a total sample size of 2,000,000 I think something like 1000 batches will be about right. Each batch will be small enough to run efficiently and not break memory constraints. You could, in theory, make each observation a separate batch, but the overhead for processing that many will become noticeably time-consuming. My best guess is that 1,000 batches is the sweetspot.

The -status- option in -runby- will have Stata give you a periodic update on the progress of the process, showing how many batches have been processed, elapsed time, and estimated time to completion.

I added -drop word*- at the end of program one_batch to ease the burden on memory--the individual word variables are not needed once the counting has been achieved.

Also be careful about that -gen int batch = ...- command. If, for some reason, you end up having to break this up into, say, 50,000 batches, you need to change -int- to -long- because -int- can't hold any number bigger than 32,740. I don't think you will actually need that many batches to get this to run efficiently, but just wanted to alert you in case it turns out to be so.

[Bjarte Aagnes]

First, an improvement of #4:

gen wordcount = wordcount(strvar)
su  wordcount, meanonly

qui forvalues i = 1/`r(max)'  {
    
   replace strvar = subinword(strvar, word(strvar,1), "", .)  + char(32) + word(strvar,1) if ( `i' <= wordcount )          
}

gen words = wordcount(strvar)
drop wordcount

Then, changing type of strvar to strL can make some improvent. Large improvents can be done if you have many identical records. Then, reduce data to one record per unique record (bysort), process the reduced dataset and merge back (frames or files). I cannot make example now, or the next days. ( Re: "but the count is not exact": 'infectious disease' stripped of single quotes will be two words...thus, some modification to the above must be implemented to adress this)

[Daniel Schaefer]

Since there are so many great Stata answers already, I just want to jump in and say I somewhat prefer python here because of the large memory requirements introduced by the split command.

import pandas
csv = pandas.read_csv("testdoc.csv")
csv["unique_word_count"] = csv["combined_words"].apply(lambda words: len(set(words.split(","))))

The approach here is to create a lambda function that splits the set of words by the comma symbol and puts the words in a hashset. Using a hashset like this allows one to find the set of unique words (and the length of that set) in linear time. Next, I apply that function to every row of the "combined_words" column and assign the result of the operation to a new column called "unique_word_count". Note that with your data you may also need to strip out whitespace characters when processing the input string.

I generated a test dataset (ironically) in R because the sample() function in R is very useful here. Using a list of the 1000 most common english words I have on my machine, I generated two datasets, one with 1 million observations and another with 2 million observations. Each observation contains 100 words sampled randomly from the set of 1000 with replacement (so repeats are fairly rare, but allowed). Running just the third line (just the algorithm itself), the first dataset takes a little over 12 seconds and the second takes a little over 19 seconds on my laptop.

I think it should be possible to get the algorithm above working in Mata. Mata doesn't support a hashset, but one should be able to treat a hashtable like a hashset. If so, it should be possible to get something with a time efficiency equivalent to the above.

[Daniel Schaefer]

Also (if you'll pardon me getting on my soapbox for a moment), single-line commands are not necessarily more time efficient than multi-line commands. It is often a useful heuristic in Stata to prefer single line commands to more complicated loops for readability reasons. Often, one liners in Stata are indeed more computationally efficient as well because the code running behind the scenes is running closer to the metal and the code is tightly optimized by a professional developer and the C compiler.

However, in general one liners tend to be less efficient than multiline solutions that use primitive operations. One liners tend to operate at a high level of abstraction, and abstraction and generalizability almost always come at the cost of computational efficiency. If your code is written in the same language as the framework that implements the abstraction, you use the same compiler/interpreter as the high-level framework, and you are as willing and able to optimize as much as the author of the framework (so holding all else equal), the general framework is going to tend to be less efficient than your custom-made primitive-heavy code that is specific to the problem at hand. There is a fundamental tradeoff between generalizability and computational efficiency.

One liners are usually (though not always) easier and more time efficient for the programmer and are often (though not always) easier to read and maintain. They are not always faster in the computational efficiency sense.

If you really want a fast algorithm, write the code in C, C++, or maybe Rust using basic primitives and data structures. It's going to take you 10 times as long to write and the code will be 100 lines instead of 1, but will almost always be several orders of magnitude faster than your one or two line solution in a high-level language.

[Mariano Mastrogiorgio]

thank you all! the runby command seems to be working. it is slow due to data size but progressing, and the status bar provides a time expectation. regards, M.

[Bjarte Aagnes]

To follow-up/close #7 above: Below is a mata solution (avoiding split) with low memory use. Example data have 1 mill obs with many duplicate strings. Assuming no commas in strings.

gen len = strlen(strvar)
. tabstat len , stat(N min p10 p25 p50 p75 p90 max)

    Variable |         N       Min       p10       p25       p50       p75       p90       Max
-------------+--------------------------------------------------------------------------------
         len |   1000000       382       704      1141      2340      4757      8083     21999
----------------------------------------------------------------------------------------------

********************************************************************************
* test mata nstrings()
********************************************************************************

use "example_data_statalist_1764113.dta" , clear

timer clear
local r 5

qui forvalues i=1/`r' {
    
    keep strvar
    noi di "running `i' " %tcHH:MM:SS now()
    
    timer on 1

     gen long nstrings = .
        mata: nstrings("strvar", "nstrings")
        
    timer off 1
}

timer list

. timer list
   1:    782.46 /        5 =     156.4918

on laptop 8G memory, Intel64 Family 6 Model 142 Stepping 10 GenuineIntel ~1600 Mhz

. tabstat nstrings , stat(N min p10 p25 p50 p75 p90 max)

    Variable |         N       Min       p10       p25       p50       p75       p90       Max
-------------+--------------------------------------------------------------------------------
    nstrings |   1000000         7        20        31        58       104       153       287
----------------------------------------------------------------------------------------------

---

Complete code example:

********************************************************************************
* repo may be deleted after some time
********************************************************************************

local url https://github.com/CancerRegistryOfNorway/

tempfile tmp

clear  

forvalues i=1/100 {
    
    copy `url'/statalist-1764113-/raw/refs/heads/main/`i'.dta "`tmp'", replace
    append using "`tmp'"
    di "`i'"
}

assert _N == 10^6
datasignature set, reset  
assert "`r(datasignature)'" == "1000000:1(64344):3026544118:3148455376"
save "example_data_statalist_1764113.dta", replace

clear all
 
********************************************************************************


********************************************************************************
* define mata function nstrings()
********************************************************************************

mata :

void nstrings(
  string scalar strvarname,
  string scalar resultvarname
) {

  string colvector strvar
  real scalar index_strvar
  real scalar index_nstrings
  real scalar i
  
  index_strvar = st_varindex(strvarname)
  index_nstrings = st_varindex(resultvarname)

  for (i = 1; i <= st_nobs(); i++) {

    strvar = tokens(_st_sdata(i, index_strvar), ",")'
    
    _st_store(
      i,
      index_nstrings,
      length(
        uniqrows(
          select(strvar, mod(1::rows(strvar), 2))
        )
      )
    )
  }
  
}

end
********************************************************************************


********************************************************************************
* test mata nstrings()
********************************************************************************

use "example_data_statalist_1764113.dta" , clear

timer clear
local r 5

qui forvalues i=1/`r' {
    
    keep strvar
    noi di "running `i' " %tcHH:MM:SS now()
    
    timer on 1

        gen long nstrings = .
        mata: nstrings("strvar", "nstrings")
        
    timer off 1
}

timer list