사용자가 양식 필드를 통해 여러 가지 응답이나 구를 게시 할 수있는 시나리오가 있습니다. 나는 응답을 받고 그들이 무엇을 요구하고 있는지를 결정할 수 있기를 바란다. 예를 들어, 사용자가 자동차, 기차, 자전거, 제트기에 타자를 치는 경우 ... 나는 그들이 차량에 대해 이야기하고 있다고 가정하고 이에 따라 대응할 수 있습니다. switch 문이나 regexp를 사용할 수도 있지만 가능한 응답 수가 많을수록 계산 효율이 떨어집니다. 문자열 그룹과 문자열을 비교하는 효율적인 알고리즘이 있는지 궁금합니다. 어떤 정보라도 좋을 것입니다.문자열을 문자열 그룹과 비교하는 가장 효율적인 알고리즘
Aho-Corasick algorithm을 살펴볼 수 있습니다. 검색하려는 문자열 모음이있는 경우 해당 문자열에서 전처리를 수행하는 데 선형 시간을 할애 할 수 있습니다. 그 시점부터 O (n) 시간에 텍스트 코퍼스에서 해당 문자열의 가능한 모든 일치를 검사 할 수 있습니다 길이 n의 즉, 알고리즘을 한 번 설정하는 사전 처리 시간이 거의 필요 없기 때문에 여러 입력을 반복 검색하여 해당 키워드를 검색 할 수 있습니다.
흥미롭게도이 알고리즘은 빠른 색인 (즉, 거대한 텍스트 본문에서 많은 다른 키워드를 찾는다)을 구축하고 다른 방법보다 10 배 뛰어난 성능을 내기 위해 특별히 고안되었습니다. 나는 그것이 당신의 어플리케이션에서 훌륭하게 작동 될 것이라고 생각합니다.
희망이 도움이됩니다.
많은 "마법"단어가있는 경우 쿼리를 단어로 분할하고 해시 기반 조회를 사용하여 단어가 인식되는지 확인하는 것이 좋습니다.
흥미롭게도, 내 접근 방식과 접근 방식을 비교하면 Rabin-Karp 알고리즘이 일반화 된 것이고 Knuts-Morris-Pratt의 일반화가 제안됩니다. :-) – templatetypedef
Trie 구조를 확인할 수 있습니다. 나는 당신의 문제에 대한 최선의 해결책 중 하나라고 생각합니다.
매력적인. FSM이 컴퓨터 과학에서 가장 과소 평가 된 개념이라고 의심하기 시작했습니다. –
@ SeanU- 나는 automata를 좋아한다. 그들은 위대하다. Aho-Corasick은 확실히 과소 평가되었습니다. – templatetypedef