感谢组织者举办这场有趣的挑战！
总结
- 从 Python 开始，使用频繁模式挖掘获得了 0.53 的公共分数。
- 切换到 C++，构建了自己的搜索器，创建了查询生成器集成，为每个测试数据行选择最佳查询，获得了 0.76 的公共分数。
原始 Python 解决方案
我最初使用 Python，并使用 FP-Growth 算法查找频繁的 CPC 和标题术语的组合。我根据这些组合匹配的目标数量进行排名，并根据估计匹配的其他非目标专利数量进行反向排名。这导致了 0.53 的公共分数。
切换到 C++
在实验中，我注意到查找随机专利的完整数据非常耗时，尤其是当这些数据包含描述时。这似乎是由 Parquet 专利数据文件仅包含单个行组（row groups）引起的，使得即使只需要单个专利的数据，也必须读取和解压缩整个文件。
与此同时，我开始考虑在提交笔记本中创建搜索索引并针对其运行查询的可能性。这将使得能够从为测试数据集中的每一行生成的查询数组中选择最佳查询。然而，使用 Whoosh 生成搜索索引需要相当多的时间。
基于这些发现，我制定了以下计划：
- 从 Parquet 文件中提取压缩的专利数据，对其内容进行分词，并将词元（tokens）以针对我的解决方案优化的格式存储到磁盘。这允许快速随机查找专利数据，以及快速查找专利字段的子集（例如，仅检索 CPC 和标题词元，而不解析其他字段的词元）。
- 在提交时，创建一个包含最可能出现在测试索引中的专利的索引。假设所有目标都存在，然后逐渐添加已在索引中的专利的热门邻居，直到索引包含 20 万专利。
索引应为每个可能的术语存储一个位集（bitset），表示匹配该术语的专利。仅考虑<category>:<token>术语，如 "ti:method" 或 "detd:algorithm"，以限制索引的大小。使用这样的索引，我们可以有效地执行使用 OR、AND、NOT 和 XOR 运算符的所有查询。
此格式不支持邻近运算符、通配符、多词术语和未分类术语。然而，我 earlier 公共分数 0.53 的提交仅使用了单项标题术语和带有 OR、AND 和 XOR 运算符的 CPC 术语，所以我确信支持的子集足以获得有竞争力的排行榜分数。 - 创建一批查询生成器，并使用它们为测试数据集中的每一行生成可能的查询，必要时进行每查询超参数优化。针对步骤 2 中创建的索引运行每个生成的查询，并提交结果最好的那个。
Along with this plan I decided to switch to C++ for optimal performance. Kaggle 笔记本运行在安装了 GCC 和 CMake 的环境中，因此我们可以在提交时编译和运行 C++ 代码。依赖项预安装在单独的笔记本中，并通过私有数据集添加。
这个计划大部分奏效，但步骤 2 有一些例外。我没有使用 20 万专利，而是最终切换到了包含所有 1300 万专利的索引。在此更改中，我放弃了对描述术语的支持以减小索引大小。我还向索引添加了计数，指示每个专利匹配每个术语的次数。这导致了在对匹配查询的专利进行排序以挑选前 50 名时的性能改进。
重新格式化的专利数据
我将原始专利数据文件转换为我的 own 格式，以允许更快的查找。对于每个专利，我重新格式化的专利数据包含所有专利的 CPC 代码、标题、摘要、权利要求和描述的无序 "token -> #occurrences" 映射。此数据以自定义二进制格式 uncompressed 存储。我将映射存储在数据文件中，并创建了一个索引文件，其中包含从出版物编号到其在数据文件中对应数据偏移量的单独映射。Together 此格式允许快速查找随机专利数据。
自定义搜索器
在构建自己的搜索器时，我注意到几个怪癖：
- XOR 解析器可能非常慢。我曾看到只有 10 个 XOR 运算符的查询在 Python 中的查询解析器中卡住。执行性能还不错，只是需要确保不要有太多的 XOR 运算符，否则提交会超时。
query_parser.parse("A OR B OR C") == query_parser.parse("(A OR B) OR C")但query_parser.parse("A XOR B XOR C") != query_parser.parse("(A XOR B) XOR C")。A XOR B XOR C被解析为((cpc:A OR cpc:B OR cpc:C) AND NOT (cpc:A AND cpc:B AND cpc:C))，而(A XOR B) XOR C被解析为((((cpc:A OR cpc:B) AND NOT (cpc:A AND cpc:B)) OR cpc:C) AND NOT ((cpc:A OR cpc:B) AND NOT (cpc:A AND cpc:B) AND cpc:C))。- 如果两个专利同样很好地匹配查询，它们的顺序由它们的 Whoosh 文档 id 决定，这似乎是一个每次将文档添加到 Whoosh 索引时增加的數字。我无法弄清楚如何在自己的搜索器中复制此顺序。
最后，我的搜索器能够在包含 20 万专利的索引上执行查询，内存索引平均不到 0.2ms，存储在磁盘上的索引平均不到 0.3ms（在我自己的笔记本电脑上的单线程中）。
查询生成器
我的最终集成由四个查询生成器组成：
- 单项生成器：此生成器用于通过生成包含单个术语的查询来测试我的实现，方法是挑选具有最大 "#targets matching the term / term selectivity" 分数的术语。它的查询表现不佳，但作为测试平台很棒。
- FP-Growth 生成器：此生成器本质上是我原始基于 Python 的提交的克隆，但现在也在抽象术语上运行（对于权利要求术语它太慢了）。
- 优化生成器：此生成器提供了我提交的大部分查询。它试图通过从将所有目标放在一个组中开始，然后贪婪地将目标从一个组交换到另一个组（或新组）来找到目标组的最佳组合。目标组通过为每个目标组创建按选择性排名的共享术语组，然后平均分配可用令牌数量 across 组来转换为查询。每个术语组内的术语然后通过隐式 AND 运算符连接在一起，而这些 AND 连接的术语组然后使用 OR 和 XOR 运算符连接在一起（查询中限制为 5 个 XOR 运算符）。
- 尽力生成器：此生成器通过不断为查询尚未匹配的最高优先级目标添加术语来迭代构建查询。例如，如果前 3 个目标匹配部分查询，此生成器检索目标 4 的术语并将选择性最低的术语添加到查询中。此生成器主要作为优化生成器无法找到好查询的情况下的 fallback。
本地验证
我在 Devin Anzelmo 的验证索引 中的前 2,500 行邻居数据上进行了本地验证。我最初使用包含 12.5 万目标和 7.5 万相关专利的内存搜索索引执行此本地验证，但后来 switched 到使用包含所有 1300 万专利的搜索索引，因为它给出了更 realistic 的结果。