파이썬에서 가장 빠른 텍스트 검색

Question

나는 (데이터베이스로 sqlite로) 첫 번째 Flask 애플리케이션을 개발 중이다. 사용자 이름을 쿼리로 사용하여이 이름에 대한 정보를 응답으로 표시합니다.

모두 잘 작동하지만 더 나은 사용자 경험을 위해 typeahead.js를 구현하고 싶습니다. Typeahead.js는 사용자 유형으로 서버에 요청을 보내고 드롭 다운에서 가능한 이름을 제안합니다. 지금 데이터베이스를 select * from table_name where name like 'QUERY%'으로 검색하고 있습니다. 그러나 이것은 당연히 그렇게 빨리는 않을 것입니다 - 작동하지만 눈에 띄는 입력 지연 (예상보다 적거나 약 1 초 정도)이 있습니다.

일부 메모리 캐싱 옵션 (예 : Redis 또는 memcached)을 살펴본 결과 속도를 높이기 위해 키 - 값 저장소가 있으므로 필요에 맞지 않는다고 생각합니다. 나는 이 가능하다고 생각한다. 옵션은 이름리스트 ([ "Jane", "John", "Jack"], 약 200k 개의 이름)를 작성하여 RAM에로드하고 거기에서 검색한다. 하지만 어떻게 플라스크의 메모리에 무언가를로드합니까?

어쨌든, 제 질문은 : (처음 몇 글자 씩) 빠른 검색 (파이썬/플라스크)을 만드는 가장 좋은 방법은 무엇입니까?

Answer 1

내 대답은 메모리에서 검색하는 방법을 알려주지 않습니다. 데이터베이스 검색을 향상시키기 위해 할 수있는 몇 가지 방법이 있다고 생각합니다. 제대로 구현되면 매우 효율적일 수 있습니다.

name 필드를 sqlite 데이터베이스에서 인덱싱했다고 가정합니다. name 필드가 색인되지 않으면 모든 검색이 매우 비효율적입니다.

색인이 있어도 검색 속도가 느릴 경우 시도 할 수있는 것은 LIKE 키워드를 사용하지 않고 대신 범위를 검색하는 것입니다. 사용자 유형 '조'는 다음과 같은 쿼리를 실행할 수 있는지

예를 들어, :

select * from table_name where name between 'Jo' and 'Joz' 

을 그래서 기본적으로 당신은 단지 쿼리 텍스트 사이에 알파벳 순서에있는 모든 가능한 이름을 찾기 위해 데이터베이스를 말해 마지막 유효한 문자가 추가 된 쿼리 텍스트

Sqlite는 이러한 유형의 검색에 인덱스를 사용하므로 성능이 훨씬 좋아집니다.

sqlite 쿼리 최적화에 대해 알고 싶으신 경우 this page은 쿼리 최적화 프로그램의 작동 방식을 설명합니다.

Answer 2

"부분 일치"를 찾고 있습니다. 모든 가능한 이름을 배열에로드하고 정렬합니다. 그런 다음 처음 두 문자의 조합에 해당하는 이름 목록의 첫 번째 요소의 인덱스를 표시하는 (26x26) 조회 배열을 별도로 만듭니다. 당신은 검색의 속도를 높일 수있는 모든 3 개의 문자 조합을 포함 할 수 있습니다 (전체 배열보다 훨씬 작은 조각으로 제한하기 때문에).

다른 말로하면 - 실제로 두 개 및 세 개의 문자 콤보를 검색하지 않을 것입니다. 당신은 배열의 조각을 반환합니다. 3 개 이상의 일치 항목을 찾으면 슬라이스를 검색 할 수 있습니다 (3자를 초과하는 테이블을 만들 가치는 없습니다).