像this这样的网站如何存储成千上万个"包含c"的单词，或者像this，"带d和c的单词"，或者even further，"解读"像CAUDK这样的单词，并发现数据库有duck个.从算法/效率的Angular 来看，他们很好奇如何实现这一点:
是使用数据库，还是将文字简单地存储在内存中并快速遍历？如果使用了数据库(每个单词都是一条记录)，您将如何进行这些查询(例如，使用PostgreSQL，contains、starts_with、ends_with和unscrambles)？
我想最简单的方法就是把所有单词都存储在内存中(排序？)，然后遍历整个百万或更少的单词列表来找到匹配项？但是解读一下呢？
基本上想知道这样做的有效方式.
"包含C"等于count(C) > 0.解读CAUDC等于count(C) <= 2 && count(A) <= 1 && count(U) <= 1 && count(D) <= 1.因此，这两个查询都可以由一个具有26个索引的数据库有效地回答，每个索引对应字母表中每个字母的计数.
下面是一个快速而肮脏的python sqlite3演示:
from collections import defaultdict, Counter
import sqlite3
conn = sqlite3.connect(':memory:')
cur = conn.cursor()
alphabet = [chr(ord('A')+i) for i in range(26)]
alphabet_set = set(alphabet)
columns = ['word TEXT'] + [f'{c}_count TINYINT DEFAULT 0' for c in alphabet]
create_cmd = f'CREATE TABLE abc ({", ".join(columns)})'
cur.execute(create_cmd)
for c in alphabet:
cur.execute(f'CREATE INDEX {c}_index ON abc ({c}_count)')
def insert(word):
counts = Counter(word)
columns = ['word'] + [f'{c}_count' for c in counts.keys()]
counts = [f'"{word}"'] + [f'{n}' for n in counts.values()]
var_str = f'({", ".join(columns)})'
val_str = f'({", ".join(counts)})'
insert_cmd = f'INSERT INTO abc {var_str} VALUES {val_str}'
cur.execute(insert_cmd)
def unscramble(text):
counts = {a:0 for a in alphabet}
for c in text:
counts[c] += 1
where_clauses = [f'{c}_count <= {n}' for (c, n) in counts.items()]
select_cmd = f'SELECT word FROM abc WHERE {" AND ".join(where_clauses)}'
cur.execute(select_cmd)
return list(sorted([tup[0] for tup in cur.fetchall()]))
print('Building sqlite table...')
with open('/usr/share/dict/words') as f:
word_set = set(line.strip().upper() for line in f)
for word in word_set:
if all(c in alphabet_set for c in word):
insert(word)
print('Table built!')
d = defaultdict(list)
for word in unscramble('CAUDK'):
d[len(word)].append(word)
print("unscramble('CAUDK'):")
for n in sorted(d):
print(' '.join(d[n]))
输出:
Building sqlite table...
Table built!
unscramble('CAUDK'):
A C D K U
AC AD AK AU CA CD CU DA DC KC UK
AUK CAD CUD
DUCK