如何高效查找50万单词的变位词并优化JSON存储？

一、速度优化：从根源避免组合爆炸 #

1. 预构建词表的变位词索引 #

先对50万词表做一次预处理，把所有3字母及以上的单词按字母排序后的字符串分组（比如"eye""yee""eey"都归到key"eey"下），同时预计算每组的字母频率，避免后续重复计算。这一步仅需执行一次，后续查询直接复用索引。

代码示例（Node.js环境）：

const readline = require('readline');
const fs = require('fs');

// 生成单词的字母频率数组（a-z对应索引0-25）
const getLetterFreq = (word) => {
  const freq = new Array(26).fill(0);
  for (const c of word.toLowerCase()) {
    const idx = c.charCodeAt(0) - 97;
    if (idx >= 0 && idx < 26) freq[idx]++;
  }
  return freq;
};

// 流式读取词表，构建变位词索引
const buildAnagramIndex = async (wordListPath) => {
  const index = new Map();
  const rl = readline.createInterface({
    input: fs.createReadStream(wordListPath),
    crlfDelay: Infinity
  });

  for await (const word of rl) {
    const trimmedWord = word.trim();
    if (trimmedWord.length < 3) continue; // 跳过短词
    const sortedKey = trimmedWord.toLowerCase().split('').sort().join('');
    if (!index.has(sortedKey)) {
      index.set(sortedKey, {
        words: [],
        freq: getLetterFreq(sortedKey)
      });
    }
    index.get(sortedKey).words.push(trimmedWord);
  }
  // 保存索引到文件，后续直接加载复用
  fs.writeFileSync('anagram-index.json', JSON.stringify(Array.from(index.entries())));
  return index;
};

2. 基于字母频率匹配，替代子单词生成 #

不再生成输入单词的所有子组合，而是先计算输入单词的字母频率，然后遍历预构建的索引，检查索引中每组的频率是否是输入频率的子集（即每组的每个字母数量都不超过输入单词的对应字母数量），符合条件的组就是所有有效的子变位词。

代码示例：

// 加载预构建的索引
const loadAnagramIndex = () => {
  const data = fs.readFileSync('anagram-index.json', 'utf8');
  return new Map(JSON.parse(data));
};

// 查找输入单词的所有有效子变位词
const findSubAnagrams = (inputWord, index) => {
  const inputFreq = getLetterFreq(inputWord.toLowerCase());
  const result = new Set(); // 自动去重

  for (const [_, { words, freq }] of index) {
    let isValid = true;
    for (let i = 0; i < 26; i++) {
      if (freq[i] > inputFreq[i]) {
        isValid = false;
        break;
      }
    }
    if (isValid) {
      words.forEach(word => result.add(word));
    }
  }

  return Array.from(result);
};

3. 额外速度优化点 #

• 用Map替代普通对象存储索引：Map的遍历和查找性能在大数据量下远优于Object。
• 流式处理词表：避免一次性将50万词加载到内存，降低内存占用同时提升处理速度。
• 预处理去重：如果词表存在重复单词，在构建索引时直接跳过重复项。

二、体积优化：压缩冗余数据 #

1. 按变位词组存储，避免重复key #

原方案可能会为每个变位词单独创建key（比如{"eye": [...], "yee": [...]}），现在改为以排序后的字符串为唯一key，每个key对应一组变位词，比如{"eey": ["eye", "yee", "eey"]}，直接减少大量重复的key条目。

2. 采用紧凑的存储结构 #

将索引存储为数组格式（[[sortedKey, [word1, word2]], ...]），比JSON对象格式节省约10%-20%的字符体积。

3. 过滤冗余数据 #

• 移除单元素变位词组：如果某个排序key下只有一个单词，且不是输入单词的必要结果，可以直接过滤（根据业务需求调整）。
• 只保留小写单词：预处理时将所有单词转为小写，避免大小写重复（比如"Eye"和"eye"视为同一单词）。

4. 可选：压缩JSON文件 #

如果最终体积仍超标，可以用zlib对JSON文件进行压缩，Node.js示例：

const zlib = require('zlib');

// 压缩索引文件
const compressIndex = () => {
  const input = fs.createReadStream('anagram-index.json');
  const output = fs.createWriteStream('anagram-index.json.gz');
  input.pipe(zlib.createGzip()).pipe(output);
};

// 读取压缩后的索引
const loadCompressedIndex = async () => {
  const buffer = await fs.promises.readFile('anagram-index.json.gz');
  const decompressed = await zlib.gunzipSync(buffer);
  return new Map(JSON.parse(decompressed.toString()));
};

效果预估 #

• 速度：预处理50万词表约5-10分钟，处理单条输入单词仅需毫秒级，1万词处理时间可控制在10分钟以内，50万词处理时间能压缩到20分钟左右。
• 体积：按分组存储并过滤冗余后，JSON索引体积可控制在30-45MB，满足50MB以内的要求。

内容的提问来源于stack exchange，提问作者Lance Pollard