내 친구 중 한 명이 최근 인터뷰에서이 문제에 직면했습니다. 나는 더 나은 해결책 & fyi를 위해 여기에 2 개의 질문을 게시하고있다.wordweb (영어 사전)에 사용 된 색인 구조
- "light"를 입력하면 드롭 다운의 제안은 대부분 "light"로 시작하고 모든 문자를 입력하고 변경할 때 나오지만 "tigress"또는 "possi"를 입력하면 제안 사항 "탈선"또는 몇 가지 다른 단어를 포함하십시오 (같은 소리 단어?). 이 제안 기능을 어떻게 달성 할 수 있습니까?
- 동의어, 반의어, 유형 및 형식 등을 저장하고 검색하는 가장 좋은 방법은 그 탭을 살펴 보는 것입니다.
나는 이것이 단순한 사전 종류의 알 고아에 의해 해결 될 수 있다고 생각하지 않는다. 샘플 코드를 작성하라는 요청을받지 않았지만이 질문은 나에게 힘든 질문입니다.
첫 번째 질문 :
I 공통 접두사 속성에 따라 트리는 데이터 구조를 사용하고 조명 관리 산출하기 위해 구축 할 것 -> 빛을. 제 추측은, 우리가 호랑이를 돌면서 다른 방향으로 가야 할 때입니다 -> 빗나가게하고, 일반적인 접미어 속성을 사용하여 트 리를 만듭니다. 즉, 문자를 문자별로, 왼쪽에서 오른쪽으로 작성하는 대신 오른쪽에서 왼쪽으로 작성할 수 있습니다. S-> S-> 전자> R-> G-> I-> t AND 빗나가 같이 해석된다 : S-> S-> 전자> R
따라서 호랑이로서 해석 될 -> g-> i-> d
처음에는 제안 사항에 해당한다고 생각합니다. 그러나 저는 처음과 끝에서 suggesting next character을 어떻게 지원할 수 있는지 배우고 싶습니다.
첫 번째 질문을 다시 작성하십시오.
edit distance은 "다른"두 단어의 척도를 제공합니다. 직접적인 구현은 단어의 마스터 목록 (사전)과 항목을 비교 한 다음 제안으로 최소 점수가있는 상위 N 단어를 제공함으로써 작동 할 수 있습니다.
나는 아마도 접두어에 근거한 제안을하기 위해 단어를 저장하기 위해 지시 된 비순환 식 워드 그래프를 사용할 것입니다. 그러나 단어 마커의 끝을위한 간단한 NULL 대신에 단어의 soundex 값.
동의어, antonyms 및 soundex 일치는 별도의 고유 한 데이터 구조 집합에 포함됩니다. 연관 배열은 작은 데이터 배열로 키/인덱스의 정렬 된 목록이 아마도 작은 단어 집합에 대해서는 괜찮을지라도 충분할 것입니다.