해시를 생성하여 영어로 동사를 검색합니다.

Question

문장에서 동사를 저장하고 검색하는 해시가 필요한 제품을 연구하고 있습니다. 나를 위해 일을 시작할 수있는 몇 가지 샘플 코드를 얻을 수 있을까요? 여기 나를 염려하는 것은 빈번하지 않은 검색과 저장의 속도입니다.

업데이트 :

찾고

A) 상수 시간 검색 O (1) b)는 흥미

Answer 1

하나의 문제는 많은 영어 단어가 동사와 명사 모두가 될 수 있다는 것입니다 문자열 (샘플 코드에 대한 기능)가 컨텍스트 만이 그 컨텍스트를 결정합니다. 예를 들어 "상황을 어떻게 생각합니까?" "Take"는 동사가 아닌 명사입니다. 많은 위양성을 초래하는 무차별 대입 접근 방식을 기꺼이 받아 들일 의향이 있습니까?

"문장에 동사를 저장하고 검색"한다는 것은 무엇을 의미합니까? 문장에서 동사를 식별하고, 추출한 다음 일종의 데이터베이스에 저장합니다. 아마도 당신의 요구 사항을 오해할까요?

Answer 2

우리의 관점에서 볼 때 이것은 아마도 (대학) 숙제 일 것입니다. 그렇다면 숙제로 표시해야합니다. C++ 0B에서

는 새로운 공식 표준 정렬되지 않은지도가 : http://en.wikipedia.org/wiki/Unordered_map_%28C%2B%2B%29

그러나이 숙제 경우 당신이 직접 구현해야 할 수 있습니다! 배열을 만들고, 좋은 해시 함수가 무엇인지 생각해보고 해고하십시오.

Answer 3

주어진 동사에 대해 고유 한 값을 생성하는 함수를 정의하여 사용자 고유의 해시 맵을 만들어보십시오. 이 값을 배열의 인덱스 또는 map의 키로 사용하십시오.

또한 인터넷에서 단어 목록 구성 및 사전을 검색하십시오. 단어 목록과 사전을 사용하는 많은 프로그램은 단어 길이에 따라 데이터 구조를 나눕니다. 또는 단어 길이는 해시 계산에 포함됩니다.

Answer 4

Ideally I would like to store all of the [verb] forms as 1 hash index

당신은 그들이 모두 공통점이 몇 가지 체크하여 소위 일반 동사와 함께 할 거의 가능하다고 생각 될 수 있습니다

   happen, happens, happened, happened, happening 

을하지만, 그것은 확실히 가능한 될 수 없습니다 소위 불규칙 동사 :

   eat, eats, ate, eaten, eating 
      sing, sings, sang, sung, singing 
      go, goes, went, gone, going 
      bring, brings, brought, brought, bringing 
      speak, speaks, spoke, spoken, speaking 

그리고 다루는 직교 대체의 변화도 있습니다 :

변화의

   try, tries, tried, tried, trying 
      cry, cries, cried, cried, crying 

그리고 다른 종류 :

   miss, misses, missed, missed, missing 

내가 제안 무엇이 infintive 양식을 가리키는 모든 동사 형태의이 같은 해시 테이블을 만드는 것입니다; 자신의 부정사 형태 포인트 : 예를 들어

  verb form 
      infinitive form 

:

다음

  happening 
      happen 


      went 
      go 


     happen 
     happen 

     go 
     go 


     ate 
     eat 

는, 동사의 형태로 제공, 당신은 매우 신속하게 hashedkey 조회를 수행하여 부정사를 찾을 수있는, 당신은 정의를 저장할 수 , 당신이 그렇게하고 싶다면 다른 테이블에서 해시 폼을 (해쉬 된) 키로 사용한다.

Answer 5

저장 용량이 극히 드물기 때문에 검색 성능이 극도로 요구되는 압도적 인 우위를 차지하는 경우처럼 완벽하게 해싱하는 것이 좋습니다. 전체 해시를 다시 생성해야하기 때문에 저장하기에는 편리하지 않지만 검색을 수행하면 결과가 O (1)로 보장됩니다. Google에서 '완벽한 해싱'을 검색하면 Bob Jenkin의 웹 사이트가 두 번째로 나열됩니다.

여기서 완벽한 해싱 구현을 확인할 수 있습니다. 자신의 코드를 참조로 사용하여 제품에서 완벽한 해싱을 구현하는 방법을 이해할 수 있습니다. (나는 과거에 이걸 가지고 성공했지만 생산을 위해서가 아니라 연구를 위해서였습니다.)