캐싱의 이유로 부울 식을 정규화하십시오. 진리 테이블보다 효율적인 방법이 있습니까?

Question

현재 프로젝트는 부울 검색 기능이있는 고급 태그 데이터베이스입니다.

funky-music and not (live or cover) 

음악 데이터베이스에있는 모든 펑키 음악을 얻을 수 있지만, 거주 또는 노래의 커버 버전 안 : 기록은 (음악 데이터베이스, 예를 들어) 등 같은 부울 식으로 쿼리되고있다.

캐싱의 경우 문제는 동일하지만 구조가 다른 쿼리가 있다는 것입니다. 예를 들어, 모건의 규칙 드 위의 쿼리를 적용하는 것은 다음과 같이 작성할 수 있습니다 : 예를 들어, 쿼리 문자열을 해싱에 의해 구현 될 것입니다 캐시 때 정확히하지만 원인 휴식 캐싱 같은 기록을 얻을 것이다

funky-music and not live and not cover 

.

그러므로 첫 번째 의도는 동일한 진리표를 구성하는 동일한 표현식을 캐싱 키로 사용할 수있는 쿼리의 진리 테이블을 만드는 것이 었습니다. 불행히도 진리표가 입력 (태그)의 수와 함께 기하 급수적으로 늘어나고 하나의 쿼리에 사용 된 태그의 수를 제한하고 싶지 않기 때문에 이것은 현실적이지 않습니다.

또 다른 접근법은 부울 대수에 의해 정의 된 규칙을 적용하는 구문 트리를 통과하여 까다로운 것으로 보이는 (최소) 정규화 된 표현을 형성 할 수 있습니다.

따라서 전체 질문은 circuit minimization 또는 진리표 (편집 : 또는 NP-hard 인 다른 알고리즘)가 필요없는 등가 쿼리에 대한 인식을 구현하는 실용적인 방법이 있습니까?

ne plus ultra는 이미 캐시 된 하위 쿼리를 인식하지만 기본 대상이 아닙니다.

Answer 1

쿼리가 "False"와 같은지 여부를 확인하는 일반적이고 효율적인 알고리즘을 사용하여 NP 완전 문제를 효율적으로 해결할 수 있으므로 찾을 가능성이 거의 없습니다.

쿼리를 표준 형식으로 변환 해보십시오. 위와 같은 이유로 특정 양식으로 변환하는 데는 매우 비용이 많이 드는 쿼리가 항상있을 것입니다. 그러나 실제로는 어떤 형식이 항상 가장 잘 작동한다는 것을 알 수 있습니다. 변환이 너무 어려워 진다면.

http://en.wikipedia.org/wiki/Conjunctive_normal_form, http://en.wikipedia.org/wiki/Disjunctive_normal_form, http://en.wikipedia.org/wiki/Binary_decision_diagram에서 확인할 수 있습니다.

Answer 2

쿼리를 결합 표준 형식 (CNF)으로 변환 할 수 있습니다. 일반적으로 SAT 해결사의 기초가되는 부울 수식의 표준적이고 간단한 표현입니다.

대개 "큰"쿼리는 연결 수가 많아서 (많은 논점이 아닌) 많은 CNF가 잘 작동해야합니다.

Answer 3

Quine-McCluskey 알고리즘은 사용자가 찾고있는 것을 달성해야합니다. Karnaugh의지도와 비슷하지만 implement in software에 쉽게 접근 할 수 있습니다.