实现基本高效 "Search" 算法:Python
Implementing Basic Efficient "Search" Algorithm: Python
模拟搜索算法
这是我的问题:
在给定的文档(string)中,例如:
"hello there my name is dominic and my name is very special"
和searchTerms(列表)如:
['my','dominic'] or ['dominic','my'] (shouldn't matter)
一种算法会 return 包含术语的文档的最短摘录:
>>> 'dominic and my'
因为
>>> 'my name is dominic'
包含的单词比之前的多。
这是我目前的想法:
通过创建一个列表来启动算法,该列表的内部列表元素数量等于搜索词的数量。在列表的每个数字内将是该搜索元素出现在文档中的索引。
document = document.split();
所以 searchTerms = ['my', 'dominic']
会 return
[[2,7], [5]]
因为 my
出现在索引 2
而 7
和 dominic
仅出现在 5
.
然后算法将采用此列表并生成所有可能性的列表:
[[2,5], [7,5]]
如您所见,文档字符串中有两个子字符串同时包含 my
和 dominic
。然后算法可以采用我做的两个内部列表的范围 max()-min()
这会告诉我文档的第二个摘录比第一个小,然后可以 return document[5:(7+1)]
这将是预期的结果。
到目前为止,我的想法是这样的:
document = "hello there my name is dominic and my name is very special"
searchTerms = ['my', 'dominic']
def answer(document, searchTerms):
index = []
document = document.split()
for a in range(0, len(searchTerms)):
index.append([i for i, x in enumerate(document) if x == searchTerms[a]])
return index
截至目前,这个 returns [[2,7],[5]]
但是我 运行 主要关注一个问题:
- 效率:
对于非常大的文档字符串和搜索词列表,此解决方案是否有效?如果不是,可以做些什么来提高效率,或者我最初的想法不好
感谢任何解决此问题的见解,谢谢。
您的算法在普通输入上的执行速度可能非常慢。假设您有 10 个搜索词和包含 10000 个单词的文本。在这种情况下,对于每个术语,您可能会有 1000 个索引的列表。这将以生成 1000^10 种可能性结束。
就大 O 符号而言,复杂度为 O((n/k)^k),其中 n 是文本中的词条数,k - 搜索词条数。
这是更快算法的想法。在逐词迭代文档时,我们需要跟踪最接近当前位置的搜索词索引。我们称此结构查找(简单 python 的字典)。快速示例:
"hello there my name is dominic and >my< name is very special"
假设我们要访问 "my" 突出显示的单词。此时lookup是{"my": 2, "dominic": 5}。当前 "my" 将更接近文本中的任何其他单词。因此,当访问下一个单词 ("name") 时,我们将更新版本 {"my": 7, "dominic": 5}。很容易看出,最优解对应于一种查找状态。因此,要获得答案,只需跟踪字典中值的 max()-min() 即可。 注意:只有当所有搜索词都作为查找键出现时,您才应该开始跟踪。
每次出现搜索词时,我们都需要从位置查找中迭代 k 个值,因此该算法的复杂度为 O(nk)。
为了让它变得更好,您还可以将 balanced BST 与查找索引一起使用。现在,您可以在 O(logk) 中检索最小索引,而不是迭代查找值 (O(k)):
min_index = bst.min()
old_index=lookup[curr_term] # O(1)
bst.delete(old_index) # O(logk)
bst.insert(new_index) # O(logk)
在这种情况下,总复杂度将为 O(nlogk)。
编辑。没有树优化的代码(在Python中没有找到内置的BST):
document = "hello there my name is dominic and my name is very special"
searchTerms = { 'my', 'dominic' } # set has faster lookups
doc_words = document.split()
from sys import maxint
def search(words, terms):
found_terms = [[i,x] for i,x in enumerate(words) if x in terms]
lookup = {}
cnt = maxint
k = len(terms)
start,end=-1,-1
for i,w in found_terms:
lookup[w] = i
if k == len(lookup):
min_idx = min(lookup.values())
curr = i - min_idx
if curr < cnt:
cnt,start,end = curr,min_idx,i
return words[start:end + 1]
模拟搜索算法
这是我的问题:
在给定的文档(string)中,例如:
"hello there my name is dominic and my name is very special"
和searchTerms(列表)如:
['my','dominic'] or ['dominic','my'] (shouldn't matter)
一种算法会 return 包含术语的文档的最短摘录:
>>> 'dominic and my'
因为
>>> 'my name is dominic'
包含的单词比之前的多。
这是我目前的想法:
通过创建一个列表来启动算法,该列表的内部列表元素数量等于搜索词的数量。在列表的每个数字内将是该搜索元素出现在文档中的索引。
document = document.split();
所以 searchTerms = ['my', 'dominic']
会 return
[[2,7], [5]]
因为 my
出现在索引 2
而 7
和 dominic
仅出现在 5
.
然后算法将采用此列表并生成所有可能性的列表:
[[2,5], [7,5]]
如您所见,文档字符串中有两个子字符串同时包含 my
和 dominic
。然后算法可以采用我做的两个内部列表的范围 max()-min()
这会告诉我文档的第二个摘录比第一个小,然后可以 return document[5:(7+1)]
这将是预期的结果。
到目前为止,我的想法是这样的:
document = "hello there my name is dominic and my name is very special"
searchTerms = ['my', 'dominic']
def answer(document, searchTerms):
index = []
document = document.split()
for a in range(0, len(searchTerms)):
index.append([i for i, x in enumerate(document) if x == searchTerms[a]])
return index
截至目前,这个 returns [[2,7],[5]]
但是我 运行 主要关注一个问题:
- 效率:
对于非常大的文档字符串和搜索词列表,此解决方案是否有效?如果不是,可以做些什么来提高效率,或者我最初的想法不好
感谢任何解决此问题的见解,谢谢。
您的算法在普通输入上的执行速度可能非常慢。假设您有 10 个搜索词和包含 10000 个单词的文本。在这种情况下,对于每个术语,您可能会有 1000 个索引的列表。这将以生成 1000^10 种可能性结束。
就大 O 符号而言,复杂度为 O((n/k)^k),其中 n 是文本中的词条数,k - 搜索词条数。
这是更快算法的想法。在逐词迭代文档时,我们需要跟踪最接近当前位置的搜索词索引。我们称此结构查找(简单 python 的字典)。快速示例:
"hello there my name is dominic and >my< name is very special"
假设我们要访问 "my" 突出显示的单词。此时lookup是{"my": 2, "dominic": 5}。当前 "my" 将更接近文本中的任何其他单词。因此,当访问下一个单词 ("name") 时,我们将更新版本 {"my": 7, "dominic": 5}。很容易看出,最优解对应于一种查找状态。因此,要获得答案,只需跟踪字典中值的 max()-min() 即可。 注意:只有当所有搜索词都作为查找键出现时,您才应该开始跟踪。
每次出现搜索词时,我们都需要从位置查找中迭代 k 个值,因此该算法的复杂度为 O(nk)。
为了让它变得更好,您还可以将 balanced BST 与查找索引一起使用。现在,您可以在 O(logk) 中检索最小索引,而不是迭代查找值 (O(k)):
min_index = bst.min()
old_index=lookup[curr_term] # O(1)
bst.delete(old_index) # O(logk)
bst.insert(new_index) # O(logk)
在这种情况下,总复杂度将为 O(nlogk)。
编辑。没有树优化的代码(在Python中没有找到内置的BST):
document = "hello there my name is dominic and my name is very special"
searchTerms = { 'my', 'dominic' } # set has faster lookups
doc_words = document.split()
from sys import maxint
def search(words, terms):
found_terms = [[i,x] for i,x in enumerate(words) if x in terms]
lookup = {}
cnt = maxint
k = len(terms)
start,end=-1,-1
for i,w in found_terms:
lookup[w] = i
if k == len(lookup):
min_idx = min(lookup.values())
curr = i - min_idx
if curr < cnt:
cnt,start,end = curr,min_idx,i
return words[start:end + 1]