stringdist crashes R with long strings

[jllipatz]

stringdist doesn't seem to behave correctly when given long strings. The following sequence causes an irrecoverable abort of the R session. I was running on Windows (32bits, memory.limit 3583), R 3.4.1.

library(sourcetools)
s<-read("D:/h2izgk/R/Bilan.txt")
nchar(s)
[1] 20521
stringdist(s,s)

[markvanderloo]

Thanks for the report. The default method in stringdist uses an ~ nchar(s)*nchar(s) size matrix, which may be too big for your machine. However this should not crash R, so that's a bug.

[jllipatz]

Actually, I was aware of this risk; Could I suggest an improvement when the goal is only the distance, not the matrix? In that case, you only need the current and the previous line of the matrix, and if you access them indirectly, eg. through pointers, you only need to swap the pointers when going to the next line, so it is almost colstless.

[markvanderloo]

yup, it's actually issue #19 :-)

[michalovadek]

great package but also facing this issue. Is there a way to compute the maximum nchar exponent that won't crash R? I tried maxing out memory.limit on a 64-bit machine with 128GB RAM but I could not get through nchar 20 000 * 80 000 and I still don't know where the upper limit lays. Sorry if there is an obvious answer but am new to this. Is there potentially a way of computing a Levenshtein-type distance on two strings with nchar around 120 000? Thanks.

[markvanderloo]

The most important memory usage of stringdist is determined by the dynamic programming matrix, which consists of double precision (64bit) numbers. So two strings of 120k characters that's 8 x 1.44E10 bytes, or about 115.2GB. On top of that is a linear cost of converting each character to an integer (but that can be neglected).

I never envisioned stringdist to be used for such long strings (and I vaguely remember that there are other approaches to compute distances between such long objects, coming mostly from biostatistics/genetics). For example, the dynamic programming matrices are indexed with C int type. Now, this is a signed integer which, according to the C standard have a maximum value of 32767 (2^15-1). You mileage may vary, depending on the compiler and platform. So it is possible that things go wrong for strings with more than 32767 characters-- at least, I can not give any guarantees, unless we know details of the compiler.

[markvanderloo]

fixed in 13f023d

Thanks again for reporting. Closing this now.