关于使用R进行字符串处理的效率问题请教

sonicworm

比如现在我有一个字符串数组，长度大概有100万，内容如以下形容词和名词组合

crucial-j_period-n

further-j_point-n

expensive-j_use-n

good-j_eye-n

enormous-j_number-n

english-j_weather-n

intellectual-j_condition-n

particular-j_form-n

total-j_form-n

emotional-j_life-n

particular-j_time-n

selected-j_information-n

important-j_role-n

different-j_time-n

artistic-j_life-n

present-j_day-n

目前我要找到包含某个形容词的字符串，如particular-j

则应找到particular-j_form-n和particular-j_time-n，这个用stringr包里面的str_locate可以做到，但是如果我有几百个甚至上千个这样的形容词要找，写循环找起来就非常慢，可能跑上整天都跑不出来，想求问高手有没有同时寻找匹配多个字符串的高效方法，非常感谢。

nan.xiao

直接并行即可。

lyxmoo

回复第2楼的肖楠：如何并行呢？

这个需求我还是认为分段 hash 是王道。

几百上千有点少，最好要缀个万级别才行。

nan.xiao

回复第3楼的 lyxmoo：嗯，有道理。

并行的话，也得看具体问题规模。另外 stringr 太低效了。

<br />
require(stringr)<br />
require(foreach)<br />
require(doMC)<br />
registerDoMC(100)</p>
<p>x = c('crucial-j_period-n', 'further-j_point-n', 'expensive-j_use-n' ...)<br />
y = c('particular-j', ...)<br />
z = vector('list', length(y))</p>
<p>z <- foreach(i = 1:length(y), .errorhandling = "pass") %dopar% {<br />
  xxx <- str_locate(x, y[i])<br />
}<br />

lyxmoo

回复第4楼的肖楠：

我觉得这100万个字串数组，全放在内存中也是可能的。

看一楼词的意思，应该是这样组成： [ 某个词 ]_j_[小的描述，有100个类？]_n

假设 _j_ 和 _n 是固定的，则很简单了

将 [某个词] 转化为一个整数，英文字典的词用一个2^20数表示够了，后面的描述用一个 2^8 描述够了。

则这个问题变成一个 2^32 的整数，这样找起来，应该是分分秒秒的事。

找某个开头，只要找从 [A] -- 的值的字串就好了。

helend

直接用正则表达式也可以吧？如果我理解的正确的话，在100万的字符串中查找1000个词组只需要488 s。当然如果用并行的话，会更快一些。

下面的代码，首先生成了一个假想随机字符串数组，在其中20%的位置包含了1000个词组，最后使用正则表达式直接查找。

</p>
<p>rm(list = ls())<br />
MHmakeRandomString <- function(n=1, lenght=12)<br />
{<br />
    randomString <- c(1:n)                  # initialize vector<br />
    for (i in 1:n)<br />
    {<br />
        randomString[i] <- paste(sample(c(0:9, letters, LETTERS),<br />
                                 lenght, replace=TRUE),<br />
                                 collapse="")<br />
    }<br />
    return(randomString)<br />
}</p>
<p>num <- 1000000<br />
pnum <- 1000<br />
set.seed(10)<br />
str <- rep('', num)<br />
pos <- unique(sort(round(runif(num * 0.2, 1, num))))<br />
p_str <- paste('particular-', seq(pnum), sep = '')<br />
str[pos] <- rep(p_str, length = length(pos))</p>
<p>strings <- paste(str, MHmakeRandomString(num), sep = '')<br />
grep_str <- paste(p_str, collapse = '|')</p>
<p>system.time(pos0 <- grep(grep_str, strings))</p>
<p>all.equal(pos, pos0)</p>
<p>

user system elapsed

485.194 2.492 488.036

lyxmoo

回复第6楼的 helend：

基本的算函数应该是这样的。

<br />
library(digest)<br />
library(bitops)</p>
<p>MHmakeRandomString <- function(n=1, lenght=12)<br />
{<br />
    randomString <- c(1:n)                  # initialize vector<br />
    for (i in 1:n)<br />
    {<br />
        randomString[i] <- paste(sample(c(0:9, letters, LETTERS),<br />
                                 lenght, replace=TRUE),<br />
                                 collapse="")<br />
    }<br />
    return(randomString)<br />
}</p>
<p>Mhash <- function( xstr, malgo="md5" ) {<br />
    xstr.a<-bitAnd( strtoi(paste("0x",substr(digest(strsplit(xstr,"_")[[1]][1],algo=malgo),1,6),sep="")),0xFFFFFF)<br />
    xstr.b<-bitAnd( strtoi(paste("0x",substr(digest(strsplit(xstr,"_")[[1]][3],algo=malgo),1,6),sep="")),0xFF)<br />
    return( bitOr(bitShiftL(xstr.a,8),xstr.b) )<br />
}</p>
<p>genStrings <- function(xnum,dig1,dig2) {</p>
<p>   return( paste(paste(paste(MHmakeRandomString(xnum,dig1),"_j_",sep=""),MHmakeRandomString(xnum,dig2),sep=""),"_n",sep="") )</p>
<p> }</p>
<p> genStrIndex <- function( xstr,malgo="md5" ) {<br />
  return(bitShiftL(bitAnd(strtoi(paste("0x",substr(digest(xstr,algo=malgo),1,6),sep="")),0xFFFFFF),8))<br />
 }</p>
<p>

lyxmoo

来100000个字串，各位自己测试,应该是生成字串很慢，但查找很快。

<br />
xstr<-genStrings(100000,8,5)</p>
<p>产生Hash,<br />
ystr<-sort(sapply(xstr,Mhash))</p>
<p>来一个找的字串<br />
xstr.tofind<-genStrIndex( substr(xstr[1000],1,8) )</p>
<p>找到它<br />
ystr[( ystr>xstr.tofind & ystr<(xstr.tofind+255) )]</p>
<p>> system.time(ystr[( ystr>xstr.tofind & ystr<(xstr.tofind+255) )])<br />
   user  system elapsed<br />
  0.030   0.000   0.026<br />

lyxmoo

回复第8楼的 lyxmoo：

也是这贴的答案

http://cos.name/cn/topic/110522

nan.xiao

楼上两位都厉害。。而且有代码有真相，好喜欢 [s:18]

cloud_wei

回复第9楼的 lyxmoo：匹配次数呢？

sonicworm

谢谢楼上各位兄弟，不过对你们所用的技巧不熟悉，我要好好看看，呵呵，非常感谢

lyxmoo

回复第11楼的 cloud wei：

<br />
> system.time( sapply(xstr[1000:1011] ,function(x) { xstr.tofind<-genStrIndex( substr(x,1,8) ) ; return(ystr[( ytr>xstr.tofind & ystr<(xstr.tofind+255) )]); } ) )<br />
 用户  系统  流逝<br />
0.920 0.032 1.272</p>
<p>sapply(xstr[1000:1011] ,function(x) { xstr.tofind<-genStrIndex( substr(x,1,8) ) ; return(ystr[( ystr>xstr.tofind & ystr<(xstr.tofind+255) )]); })<br />
NyYwjMnL_j_6NdBZ_n.NyYwjMnL_j_6NdBZ_n KPZPFN9V_j_Zubbh_n.KPZPFN9V_j_Zubbh_n<br />
                           3505033736                            1931777355<br />
VjyGOuMb_j_Vf3rR_n.VjyGOuMb_j_Vf3rR_n eu6dx1iO_j_ZjwRv_n.eu6dx1iO_j_ZjwRv_n<br />
                           2313865837                            4139294180<br />
Y9JN5Q4s_j_TZnjU_n.Y9JN5Q4s_j_TZnjU_n 8yvjahxT_j_FgMC4_n.8yvjahxT_j_FgMC4_n<br />
                           2327978535                            2686627797<br />
dDKCZzd2_j_YnbZp_n.dDKCZzd2_j_YnbZp_n xfvasf4b_j_jFP47_n.xfvasf4b_j_jFP47_n<br />
                           2933496729                            3296638641<br />
eM6fPV9l_j_jKP3X_n.eM6fPV9l_j_jKP3X_n v9VfjsMw_j_iZ7DU_n.v9VfjsMw_j_iZ7DU_n<br />
                           1104760301                            3539185338<br />
717q2FOF_j_Y6upc_n.717q2FOF_j_Y6upc_n 95Xle7C3_j_hCQOG_n.95Xle7C3_j_hCQOG_n<br />
                           2152958512                            4010003722 </p>
<p>

看来没想像的快，从10万个中查10个，就要用1秒那么久。100 个词居然要用 15 秒。

还有就是如果字串中第一段的出现的词太多，会Hash碰撞, 找出不匹配的词，咱是假设它是字典上的词，用 2^24 来盖；

太云是说找到的词出现次数？

由于这里是随机8字符的字串，不好演示，应该会将那一个hash段内出现的词都显示出来的。

lyxmoo

回复第13楼的 lyxmoo：

改用 which ，提高了一点点，但是还是不够。

<br />
> system.time(sapply(xstr[1000:1100] ,function(x) { xstr.tofind<-genStrIndex( substr(x,1,8) ) ; return(which( ysr>xstr.tofind & ystr<(xstr.tofind+255) ) ); }) )<br />
  用户   系统   流逝<br />
10.460  0.292 12.246 </p>
<p>

看来要上 factor.

sonicworm

可惜论坛不能传数据，如果可以我发上来，大家可以测试一下，不知道有QQ群么

sonicworm

对了，我看了上边兄弟们的代码，有个疑问，虽然我找的是字符串，但是其实我需要的是字符串在原来数组中的位置(index)，因为每个位置对应于一组用于模式识别的数据，我需要通过查找字符串来找到包含这些字符串的index,比如1楼的例子，我希望通过查找“particular”得到7,10，如以0为数组下标起始的话。诚心求教，谢谢大家。

sonicworm

我发现6楼的正则表达式方法可行，唯一遗憾的就是待查找字符串超过一定数目表达式就无效了。

helend

回复第17楼的 sonicworm：

你测试了多大的数目？

你可以并行运算。

sonicworm

回复第18楼的 helend：3000多个字符串就不行了

sonicworm

另外正则表达式效率也不算高，100万个字符串里面找2000个就用了3491.469秒，如果找10000个以上时间就没法说了