CPU-and-memory efficient NGram extraction with R

Question

我写了一个算法，从 50000 个街道地址的列表中提取 NGram（二元语法、三元语法、...直到 5 元语法）。我的目标是为每个地址提供一个布尔向量，表示该地址中是否存在 NGram。因此每个地址都将由一个属性向量来表征，然后我可以对这些地址进行聚类。该算法以这种方式工作：我从二元语法开始，计算（a-z 和 0-9 和/和制表）的所有组合：例如：aa,ab,ac,...,a8,a9,a/,a ,ba, bb,... 然后我为每个地址执行一个循环并为所有二元组提取信息 0 或 1（二元组不存在或不存在）。之后，我计算出现次数最多的二元组。等等 ... 我的问题是算法达到运行所花费的时间。另一个问题：当超过 10000 个 NGram 时，R 达到其最大容量。这很明显，因为 50000*10000 的矩阵很大。我需要你的想法来优化算法或改变它。谢谢。

Answer 1

其中一些问题在某种程度上已经被 tm 库和 RWeka（用于 n-gram 标记化）解决了。看看那些，它们可能会使您的任务更容易。

对于运行内存不足，我看到两个选项：

tm 使用稀疏矩阵，这是一种存储具有许多零元素的矩阵的有效方法。
您还可以查看 bigmemory 包。虽然，我没用过http://cran.r-project.org/web/packages/bigmemory/index.html

有很多方法可以加速 R 代码。以下是一些操作方法的指南：http://www.r-bloggers.com/faster-higher-stonger-a-guide-to-speeding-up-r-code-for-busy-people/

Answer 2

使用此方法尝试 quanteda 包。如果您只想要标记化的文本，请将 dfm( 替换为 tokenize(。

我非常想知道它在您的 50,000 个街道地址上的工作原理。我们付出了很多努力使 dfm() 变得非常快速和强大。

myDfm <- dfm(c("1780 wemmel", "2015 schlemmel"), what = "character", 
             ngram = 1:5, concatenator = "", 
             removePunct = FALSE, removeNumbers = FALSE, 
             removeSeparators = FALSE, verbose = FALSE)
t(myDfm) # for easier viewing
#         docs
# features text1 text2
#           1     1
# s         0     1
# sc        0     1
# sch       0     1
# schl      0     1
# w         1     0
# we        1     0
# wem       1     0
# wemm      1     0
# 0         1     1
# 0         1     0
# 0 w       1     0
# 0 we      1     0
# 0 wem     1     0
# 01        0     1
# 015       0     1
# 015       0     1
# 015 s     0     1
# 1         1     1
# 15        0     1
# 15        0     1
# 15 s      0     1
# 15 sc     0     1
# 17        1     0
# 178       1     0
# 1780      1     0
# 1780      1     0
# 2         0     1
# 20        0     1
# 201       0     1
# 2015      0     1
# 2015      0     1
# 5         0     1
# 5         0     1
# 5 s       0     1
# 5 sc      0     1
# 5 sch     0     1
# 7         1     0
# 78        1     0
# 780       1     0
# 780       1     0
# 780 w     1     0
# 8         1     0
# 80        1     0
# 80        1     0
# 80 w      1     0
# 80 we     1     0
# c         0     1
# ch        0     1
# chl       0     1
# chle      0     1
# chlem     0     1
# e         2     2
# el        1     1
# em        1     1
# emm       1     1
# emme      1     1
# emmel     1     1
# h         0     1
# hl        0     1
# hle       0     1
# hlem      0     1
# hlemm     0     1
# l         1     2
# le        0     1
# lem       0     1
# lemm      0     1
# lemme     0     1
# m         2     2
# me        1     1
# mel       1     1
# mm        1     1
# mme       1     1
# mmel      1     1
# s         0     1
# sc        0     1
# sch       0     1
# schl      0     1
# schle     0     1
# w         1     0
# we        1     0
# wem       1     0
# wemm      1     0
# wemme     1     0

CPU-and-memory efficient NGram extraction with R

CPU-and-memory efficient NGram extraction with R

performance

r

text-mining

n-gram