- jieba & inverted index
- Brute-force method
First use jieba.lcut to cut words in each line, if the result length of word is shorter
than 3, I'll concate the character besides it until the length is longer than 3
words2 = jieba.lcut(line, cut_all=True)
for index, word in enumerate(words2):
l = len(word)
words_len = len(words2)
if l > 1:
trie.insert(word, i+1)
if l == 1:
find_index = line.find(word)
if find_index == 0:
if line_len > 1:
trie.insert(word + line[1], i+1)
if line_len > 2:
trie.insert(word + line[1] + line[2], i+1)
elif find_index == 1:
trie.insert(line[0] + word, i+1)
if line_len > 2:
trie.insert(word + line[2], i+1)
trie.insert(line[0] + word + line[2], i+1)
if line_len > 3:
trie.insert(word + line[2] + line[3], i+1)
elif find_index == line_len-1:
trie.insert(line[find_index-1] + word, i+1)
trie.insert(line[find_index-2] + line[find_index-1] + word, i+1)
elif find_index == line_len-2:
trie.insert(line[find_index-1] + word, i+1)
trie.insert(word + line[find_index+1], i+1)
trie.insert(line[find_index-2] + line[find_index-1] + word, i+1)
trie.insert(line[find_index-1] + word + line[find_index+1], i+1)
else:
trie.insert(line[find_index-2] + line[find_index-1] + word, i+1)
trie.insert(line[find_index-1] + word + line[find_index+1], i+1)
trie.insert(word + line[find_index+1] + line[find_index+2], i+1)
trie.insert(line[find_index-1] + word, i+1)
trie.insert(word + line[find_index+1], i+1)
if l == 2:
find_index = line.find(word)
if find_index == 0:
if line_len > 2:
trie.insert(word + line[2], i+1)
trie.insert(word[1] + line[2], i+1)
elif find_index == line_len-2:
trie.insert(line[find_index-1] + word, i+1)
trie.insert(line[find_index-1] + word[0], i+1)
else:
trie.insert(line[find_index-1] + word, i+1)
trie.insert(line[find_index-1] + word[0], i+1)
trie.insert(word + line[find_index+2], i+1)
trie.insert(word[1] + line[find_index+2], i+1)
trie.insert is to build a trie-tree and trie.search is to find the word in tree
Read every line in query.txt, if find query in line then append to the list.
for x in lines:
op = re.split(' |\n',x)
query_times = len(op) / 2
list1 = search(op[0])
list2 = search(op[2])
if op[1] == "and":
ans = list(set(list1) & set(list2))
if query_times == 3:
list3 = search(op[4])
ans = list(set(ans) & set(list3))
elif op[1] == "or":
ans = list(set(list1) | set(list2))
if query_times == 3:
list3 = search(op[4])
ans = list(set(ans) | set(list3))
elif op[1] == "not":
ans = list(set(list1) - set(list2))
if query_times == 3:
list3 = search(op[4])
ans = list(set(ans) - set(list3))
if len(ans) == 0:
file.write('0')
if count != count_lines:
file.write('\n')
else:
file.write(','.join(str(v) for v in sorted(ans, key=int)))
if count != count_lines:
file.write("\n")
count += 1
| method | time |
|---|---|
| jieba & inverted index | Brute-force |
| 29 | 0.27 |
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent