4

我正在编写一些 Python 代码来实现我最近学习的一些与倒排索引/发布列表相关的概念。我对 Python 很陌生，在某些情况下很难理解它的效率。

从理论上讲，创建一组文档 D 的倒排索引，每个文档都有一个唯一的 ID，doc_id应该包括：

  1. 解析/执行 D 中每个文档的词法分析
  2. 删除停用词，执行词干等。
  3. 创建所有(word,doc_id)对的列表
  4. 对列表进行排序
  5. 将重复项压缩为{word:[set_of_all_doc_ids]} （倒排索引）

第 5 步通常是通过一个包含带有元数据（词频、字节偏移）的词和指向发布列表（它出现在其中的文档列表）的指针的字典来执行的。发布列表通常被实现为允许有效随机插入的数据结构，即链表。

我的问题是 Python 是一种高级语言，直接使用内存指针（以及链表）之类的东西似乎超出了范围。我在分析之前进行了优化，因为对于非常大的数据集，众所周知，必须最大化效率才能在合理的时间内保留任何计算索引的能力。

SO上有其他几篇关于Python倒排索引的帖子，就像我当前的实现一样，它们使用字典将键映射到列表（或集合）。是否期望这种方法与允许直接编码指向链表的指针的语言具有相似的性能？

4

2 回答 2

3

有很多话要说：

  1. 如果特定列表实现需要随机访问，则链表不是最佳的（无论使用哪种编程语言）。要访问列表的第 i 个元素，链表要求您从第 0 个元素一直迭代到第 i 个元素。相反，列表应该存储为一个连续的块（如果它很长，则应存储为几个大块）。Python 列表[...]是以这种方式存储的，所以首先，一个 Python 列表就足够了。

  2. 在 Python 中，任何不是基本数据类型（例如or ）的对象的赋值都是通过 传递一个指针并将引用计数递增到 来在内部执行的。因此，如果是列表或字典（或用户定义的类，就此而言），原则上这与在 C 或 C++ 中传递指针没有太大区别。a = bbintfloatbb

  3. 但是，显然a) 引用计数和 b) 垃圾收集会导致一些开销。如果实现是为了学习目的，即更好地理解倒排索引的概念，我不会担心。但是对于一个严肃的、高度优化的实现，使用纯 Python（而不是嵌入到 Python 中的例如 C/C++）是不可取的。

  4. 当您进一步优化发布列表的实现时，您可能会看到需要 a) 进行随机插入，b) 保持排序和 c) 保持压缩 - 所有这些都同时进行。到那时，标准的 Python 列表将不再足够好，您可能希望研究在C/C++中实现更优化的列表表示并将其嵌入到 Python 中。然而，即便如此，仍然可能坚持使用纯 Python。例如，您可以使用大字符串来实现列表，并以某种方式使用itertools和buffer访问特定部分，这在某种程度上类似于指针算术。

  5. 在 Python中处理字符串时应始终牢记的一件事是，尽管我在上面提到了赋值操作，但substring操作text[i:j]涉及创建 substring 的实际（深层）副本，而不仅仅是增加引用计数。这可以通过使用buffer上面提到的数据类型来避免。

于 2012-03-04T04:14:26.637 回答
-1

您可以在以下位置查看 Python 中倒排索引的代码和文档：http ://www.ssiddique.info/creation-of-inverted-index-and-use-of-ranking-algorithm-python-code.html

很快我将用 C++ 对其进行编码..

于 2012-03-23T01:20:44.007 回答