有人了解 google 的 regular expression search 是怎么实现的吗 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

有人了解 google 的 regular expression search 是怎么实现的吗

有人了解 google 的 regular expression search 是怎么实现的吗# JobHunting - 待字闺中

r*r2012-09-17 07:09

1 楼

For example, "love * price", 其中的 * 代表一个或多个单词，相当于 RE 中的
star 字符, 因此这个搜索串可以 match:
love the price
love its low price
love its really low price
etc.
像这种搜索，如何实现，如何建立索引？

d*o2012-09-17 07:09

2 楼

对于你给的例子，可以做一个trie这样的结构这样所有以love开始的query就可以找到
然后，对于所有的以love开始的query，再看是否match “* price”这个RE。
当然，为了后面的快一些，也可以建立一个反向的trie，索引是从后往前，比如可以找
到所有以price结尾的query。这样反向trie和正向trie的交集就是了。

【在 r******r 的大作中提到】

: For example, "love * price", 其中的 * 代表一个或多个单词，相当于 RE 中的
: star 字符, 因此这个搜索串可以 match:
: love the price
: love its low price
: love its really low price
: etc.
: 像这种搜索，如何实现，如何建立索引？

r*r2012-09-17 07:09

3 楼

两个 trie, 找交集，好像是一种思路？
但是在 apache lucene 中，可以大规模的这样建立 trie 这种结构, 以 index 大规模
数据集吗？不是很了解这一块。

【在 d****o 的大作中提到】

: 对于你给的例子，可以做一个trie这样的结构这样所有以love开始的query就可以找到
: 然后，对于所有的以love开始的query，再看是否match “* price”这个RE。
: 当然，为了后面的快一些，也可以建立一个反向的trie，索引是从后往前，比如可以找
: 到所有以price结尾的query。这样反向trie和正向trie的交集就是了。