第一名解决方案

感谢主办方举办这场有趣的竞赛。恭喜获胜的团队。也感谢 @tomyanabe 与我同台竞技。

总结

• 模拟退火 (Simulated Annealing)
• 仅使用 AND, OR
• 使用 - 省略 AND

查询

查询格式如下:
(ti:word1-ti:word2-detd:word3-…-cpc:wordN) OR …

• 查询仅由 AND 和 OR 组成
• 通过用 - 连接单词，可以省略 AND 标记
• cpc 不能用 - 省略，因此 cpc 放在最后
• cpc、title、abstract 使用所有单词
• 对于 claim 和 description，删除高频词（100,000 或以上）

候选生成

将通过 AND 连接的单词序列定义为子查询。
通过以下步骤生成用于查询的子查询候选：

1. 生成用于子查询的单词集合
   • 单个目标拥有的所有单词
   • 两个目标拥有的单词交集
2. 按元素数量对单词排序
3. 添加单词直到专利集合仅包含目标，并将其制成子查询
   • 专利集合通过取每个单词的交集获得
   • 如果组合所有单词后存在非目标，则该子查询不是候选

改进技巧

• 按元素升序添加单词以降低计算复杂度
  • 计算两个集合 s, t 交集的复杂度为 min(len(s), len(t))
• 使用 cupy 加速交集计算
  • 比使用 set(a) & set(b) 快 2-3 倍
  • cp.intersect1d(array1, array2)
  • 在最后一天，通过此加速可以使用所有 cpc、title、abstract，排名从第 3 名提升至第 1 名
• 仅将 test.csv 中出现的专利 (2500*50) 及其拥有的单词放入内存，以减少内存使用

模拟退火

• 用 OR 组合子查询
• 邻域
  • 50% 几率添加一个未使用的子查询
  • 50% 几率移除一个已使用的子查询
• 评分函数
  • 查询搜索结果中包含的目标数量
  • 仅考虑目标数量，因为候选是零非目标的子查询
• 去重
  • 通过去除重复项减少候选数量，因为具有相同目标集合的子查询不需要多个候选

代码