我知道全文搜索的一个基本方面是使用倒排索引.因此,使用反向索引,单字查询变得微不足道.假设索引的结构如下:

some-word - > [doc385,doc211,doc39977,...](按等级排序,降序排序)

要回答该单词的查询,解决方案就是在索引中找到正确的条目(需要O(log n)时间)并从索引中指定的列表中显示一些给定数量的文档(例如前10个).

但是那些返回与两个单词相匹配的文档的查询呢？最直接的实现如下:

1. 将A设置为具有单词1的文档集(通过搜索索引).
2. 将B设置为具有单词2(同上)的文档集.
3. 计算A和B的交点.

现在,第三步可能需要O(n log n)时间来执行.对于非常大的A和B,可能使查询缓慢回答.但像谷歌这样的搜索引擎总会在几毫秒内回复他们的答案.所以这不是完整的答案.

一个明显的优化是,由于像谷歌这样的搜索引擎无论如何都没有返回所有匹配的文档,我们不必计算整个交集.我们可以从最小的集合(例如B)开始,并找到足够的条目,这些条目也属于另一个集合(例如A).

但是,我们还不能有以下最糟糕的情况吗？如果我们设置A是与普通单词匹配的文档集,并且集合B是与另一个常用单词匹配的文档集,则可能仍然存在A∩B非常小的情况(即,组合很少).这意味着搜索引擎必须线性地遍历B的所有元素x成员,检查它们是否也是A的元素,以找到符合这两个条件的少数元素.

线性不快.并且您可以使用两个以上的单词进行搜索,因此仅使用并行性肯定不是整个解决方案.那么,这些案例如何优化？大型全文搜索引擎是否使用某种复合索引？布隆过滤器？有任何想法吗？

我读过Doug Cutting的论文; " 总排名的空间优化 ".

由于它是很久以前写的,我想知道lucene使用什么算法(关于帖子列表遍历和分数计算,排名).

特别是,那里描述的总排名算法涉及遍历每个查询词的整个帖子列表,因此在非常常见的查询词如"黄狗"的情况下,2个词中的任何一个可能具有非常长的帖子列表,如果是网络搜索.它们是否真的遍及当前的Lucene/Solr？或者是否有任何启发式方法来截断所使用的列表？

在只返回前k个结果的情况下,我可以理解,在多个机器上分发发布列表,然后组合每个机器的top-k可以工作,但是如果我们需要返回"第100个结果页面",即结果排名从990-1000,然后每个分区仍然必须找出前1000,所以分区将没有多大帮助.

总的来说,有没有关于Lucene使用的内部算法的最新详细文档？

搜索引擎如何合并倒排索引的结果？

例如,如果我搜索单词"dog"和"bat"的倒排索引,那么每个文档中都会有两个巨大的列表,其中包含两个单词中的一个.

我怀疑搜索引擎是否遍历这些列表,一次一个文档,并尝试查找与列表结果匹配的内容.算法做了什么使这个合并过程快速发展？

更新2015-10-15

早在2012年,我正在构建个人在线应用程序,并且实际上想要重新发明轮子,因为我天生好奇,出于学习目的并提高我的算法和架构技能.我可以使用apache lucene和其他人,但正如我所提到的,我决定建立自己的迷你搜索引擎.

问:除了使用elasticsearch,lucene等可用服务之外,真的没有办法增强这种架构吗？

原始问题

我正在开发一个Web应用程序,用户在其中搜索特定的标题(例如:book x,book y等),这些数据位于关系数据库(MySQL)中.

我遵循的原则是,从db中获取的每条记录都缓存在内存中,以便应用程序对数据库的调用较少.

我开发了自己的迷你搜索引擎,具有以下架构:

这是它的工作原理:

• a)用户搜索记录名称
• b)系统检查查询开始的字符,检查是否在那里查询:获取记录.如果没有,请添加它并使用两种方式从数据库中获取所有匹配的记录:
  • 在表"查询"(这是一种历史表)中已经存在查询,从而根据ID获得记录(快速性能)
    
  • 或者,否则使用Mysql LIKE %%语句来获取记录/ ids(同时在历史表查询中保留用户使用的查询以及它映射到的ids).
    - >然后它将记录及其ID添加到 缓存中,并且只将id添加到反向索引映射中.
• c)将结果返回给UI

系统工作正常,但我有两个主要问题,我找不到一个好的解决方案(过去一个月一直在尝试):

第一个问题:
如果你检查点(B),情况没有查询"历史"被发现,它必须使用像%%声明:此过程变得时间当查询数据库(而不是一个或匹配许多纪录消耗二):

• 从Mysql获取记录需要一些时间(这就是我在特定列上使用INDEXES的原因)
• 然后是时间保存查询历史记录
• 然后是时候将记录/ ID添加到缓存和反向索引映射

第二个问题:
应用程序允许用户添加自己的新记录,这些记录可以立即被登录到应用程序的其他用户使用.
然而,为了实现这一点,必须更新反向索引映射和表"查询",以便在任何旧查询与新单词匹配的情况下.例如,如果添加了新记录"woodX",旧的查询"wood"仍会映射到它.所以为了重新勾选查询"wood"到这个新记录,这就是我现在正在做的事情:

• 新记录"woodX"被添加到"记录"表中
• 然后我运行一个Like %%语句来查看表"查询"中哪些已存在的查询映射到此记录(例如"wood"),然后将此查询与新记录ID一起添加为新行:[wood,new ID].
• 然后在内存中,通过将新记录ID添加到此列表来更新反向索引Map的"木"键值(即列表)

- >现在,如果远程用户搜索"wood",它将从内存中获取:wood和woodX

这里的问题也是时间消耗.将所有查询历史(在表查询中)与新添加的单词匹配需要花费大量时间(匹配查询越多,时间越多).然后内存更新也需要很多时间.

什么,我想这样做来解决这个问题的时候,就是返回了预期的结果,用户第一,然后让应用程序发布一个AJAX所要求的数据呼叫,实现所有这些更新任务.但我不确定这是一种不良做法还是一种不专业的做事方式？
所以在过去的一个月(多一点)我试着想到这个架构的最佳优化/修改/更新,但我不是文档检索领域的专家(实际上它是我的第一个迷你搜索引擎).

我将非常感谢能够实现这种架构的任何反馈或指导.
提前致谢.

PS:

• 它是一个使用servlet的j2ee应用程序.
• 我正在使用MySQL innodb(因此我无法使用全文搜索选项)

我有一个嵌套python字典形式的完整倒排索引.其结构是:

{word : { doc_name : [location_list] } }

例如,让字典称为索引,然后对于单词"spam",条目看起来像:

{ spam : { doc1.txt : [102,300,399], doc5.txt : [200,587] } }

我使用这个结构,因为python dict非常优化,它使编程更容易.

对于任何"垃圾邮件"这个词,包含它的文件可以通过以下方式给出:

index['spam'].keys()

并通过以下方式发布文档doc1的列表:

index['spam']['doc1']

目前我正在使用cPickle来存储和加载这本字典.但是pickle文件大约是380 MB并且需要很长时间才能加载 - 112秒(大约我使用time.time()定时)并且内存使用量达到1.2 GB(Gnome系统监视器).一旦它加载,它的罚款.我有4GB内存.

len(index.keys()) 给出了229758

码

import cPickle as pickle

f = open('full_index','rb')
print 'Loading index... please wait...'
index = pickle.load(f)  # This takes ages
print 'Index loaded. You may now proceed to search'

如何让它加载更快？我只需要在应用程序启动时加载一次.之后,访问时间对于响应查询很重要.

我应该切换到像SQLite这样的数据库并在其键上创建索引吗？如果是,我如何存储值以具有等效模式,这使得检索变得容易.还有什么我应该研究的吗？

附录

使用添的回答pickle.dump(index, file, -1)腌制文件相当小-围绕237 MB(花了300秒时间来转储)......并采取一半立即加载(61秒的时间......而不是112分更早的.... 了time.time ())

但是我应该迁移到数据库以获得可伸缩性吗？ …

我正在阅读有关倒排索引(由Solr,Elastic Search等文本搜索引擎使用)和我理解(如果我们以"Person"为例):

Person关系的属性被反转:

John -> PersonId(1), PersonId(2), PersonId(3)
London -> PersonId(1), PersonId(2), PersonId(5)

我现在可以搜索"居住在伦敦的约翰"的人事记录

这不解决所有问题吗？为什么我们有前向(或常规数据库索引)？或者换句话说,在什么情况下常规索引是有用的？请解释.谢谢.

我正在为一组文档上的搜索引擎编写倒排索引.现在,我将索引存储为字典词典.也就是说,每个关键字都映射到docIDs->发生位置的字典.

数据模型类似于:{word:{doc_name:[location_list]}}

在内存中构建索引工作正常,但是当我尝试序列化到磁盘时,我遇到了一个MemoryError.这是我的代码:

# Write the index out to disk
serializedIndex = open(sys.argv[3], 'wb')
cPickle.dump(index, serializedIndex, cPickle.HIGHEST_PROTOCOL)

在序列化之前,我的程序使用大约50%的内存(1.6 Gb).一旦我打电话给cPickle,我的内存使用率在崩溃之前就会猛增至80%.

为什么cPickle使用如此多的内存进行序列化？有没有更好的方法来解决这个问题？

我正在实现一个反向索引结构,特别是允许布尔查询和字级粒度的结构.

我有一个大型的文本数据库,我保留一个索引,告诉我,对于每个单词,它在哪个文件中(IDdoc),以及文件在哪里(position).(一个单词可以在许多文件中,也可以在一个文件中的许多位置.)

因此,我为每个单词保留一个向量:

vector<pair<IDdoc,position>> occurences_of_word;

(向量按IDdoc排序,然后按位置按升序排序.)

我有一个string用文字构成的对象.这是我正在寻找的短语.

对于短语中的每个单词,我想知道哪些文档包含该短语,因此返回s 的向量.IDdoc

这是我尝试解决方案:

typedef std::string     Word_t;
typedef unsigned int    WordPosition_t;
typedef unsigned int    IDdocument_t;

vector<pair<IDdocument_t,WordPosition_t> > IndiceInvertidoBooleanoConPosicion::_interseccion_dos_listas
    (const vector<pair<IDdocument_t,WordPosition_t>> & v1,
    const vector<pair<IDdocument_t,WordPosition_t>> & v2)
{
vector<pair<IDdocument_t,WordPosition_t> > intersection;

IDdocument_t ID_doc_one, ID_doc_two;

int i = 0;
int j = 0;
const int MAX_INDEX_V1 = v1.size() -1;
const int MAX_INDEX_V2 = v2.size() -1;

while(i <= MAX_INDEX_V1  && …

问题:您需要使用哪种解决方案或技巧来处理一个非常大(多TB)的数据库,该数据库在具有高冗余的强哈希上编制索引？

某种倒置存储？

Postgres有什么可以做的吗？

如果需要,我准备推出自己的存储空间.

(提示:必须是开源的,没有Java,必须在Linux上运行,必须基于磁盘,首选C/C++/Python)

细节:

我需要创建一个非常大的数据库,其中每个记录具有:

• 一些任意元数据(一些文本字段),包括一些主键
• 一个哈希值(128位哈希值,强MD5样)

记录的数量是我认为非常大的数量:几十到十亿的数十亿.跨行的哈希存在显着的冗余(超过40%的记录的哈希与至少另一条记录共享,一些哈希存在于100K记录中)

主要用法是通过哈希查找,然后检索元数据.次要用法是按主键查找,然后检索元数据.

这是一个分析型数据库,因此总体负载是中等的,主要是读取,少量写入,主要是批量写入.

当前的方法是使用Postgres,主键上有索引,哈希列上有索引.该表是批量加载的,并且关闭了散列上的索引.

所有索引都是btree.哈希列上的索引越来越大,比表本身大或大.在120 GB的表上,重新创建索引大约需要一天.查询表现相当不错.

问题是目标数据库的预计大小将超过4TB,基于400GB的较小数据集的测试,约占总目标的10%.一旦加载到Postgres中,遗憾的是,超过50%的存储被哈希列上的SQL索引使用.

这太大了.我觉得哈希中的冗余是存储更少的机会.

另请注意,虽然这描述了问题,但是需要创建一些这样的表.

这是我对两者的理解

B 树索引 :-一般用于数据库列。它将列内容保留为 key 并将 row_id 保留为 value 。它以排序方式保持键以快速找到键和行位置

倒排索引：-一般用于全文搜索。此处，文档中的单词也用作键，以排序方式与文档位置/ID 一起存储为值。

那么 b/w B tree index 和 Inverted index 有什么区别。对我来说它们看起来一样