normaliza la expresión booleana por razones de almacenamiento en caché. ¿hay una manera más eficiente que las tablas de verdad?

Mi proyecto actual es una base de datos de etiquetas avanzada con funciones de recuperación booleana. Los registros se va a consultar con expresiones booleanas como tales (por ejemplo, en una base de datos de música):normaliza la expresión booleana por razones de almacenamiento en caché. ¿hay una manera más eficiente que las tablas de verdad?

funky-music and not (live or cover)

que debe rendir toda música funky en la base de datos de música, pero no vivir o versiones de las canciones.

Cuando se trata de almacenar en caché, el problema es que existen consultas que son equivalentes pero de estructura diferente. Por ejemplo, la aplicación de la regla de Morgan la consulta anterior podría escribirse así:

funky-music and not live and not cover

lo cual produciría exactamente los mismos registros, pero de causa caché de descanso cuando se pondría en práctica mediante hash de la cadena de consulta, por ejemplo, el almacenamiento en caché.

Por lo tanto, mi primera intención fue crear una tabla de verdad de la consulta que luego podría usarse como clave de almacenamiento en caché como expresiones equivalentes de la misma tabla de verdad. Desafortunadamente, esto no es posible ya que la tabla de verdad crece exponencialmente con el número de entradas (etiquetas) y no quiero limitar el número de etiquetas utilizadas en una consulta.

Otro enfoque podría ser atravesar el árbol de sintaxis aplicando reglas definidas por el álgebra booleana para formar una representación normalizada (mínima) que también parece ser difícil.

Por lo tanto, la pregunta general es: ¿existe una forma practicable de implementar el reconocimiento de consultas equivalentes sin la necesidad de circuit minimization o tablas de verdad (edición: o cualquier otro algoritmo que sea NP-hard)?

El ne plus ultra reconocería las subconsultas ya en caché, pero ese no es el objetivo principal.

Fuente

2011-05-01 user733321

utilice la tecla bit a bit, p. Ej. establecer bit 0 si funky | bit 6 0 = live/1 = studio | bit 8 rap | bit 9 pop luego utiliza operaciones bit a bit para determinar la representación de clave en la consulta tiene sentido? – Dan

este es un patrón común entre desarrolladores móviles - createScreen (long style_element) donde long style_element es el resultado final de dichas manipulaciones bit a bit y dicta elementos de estilo indescriptibles (verdaderamente lol) para dicho objeto Screen – Dan

Esto sería una forma eficiente de memoria para almacenar la información en la base de datos. Pero ese es un tema completamente diferente. – user733321

Un algoritmo general y eficiente para determinar si una consulta es equivalente a "False" se podría utilizar para resolver problemas NP-complete de manera eficiente, por lo que es poco probable que encuentre uno.

Puede intentar transformar sus consultas en una forma canónica. Debido a lo anterior, siempre habrá consultas que son muy caras de transformar en cualquier forma dada, pero es posible que, en la práctica, algunas formas funcionen bastante bien la mayor parte del tiempo, y siempre se puede abandonar a la mitad de un formulario. transformación si se está volviendo demasiado difícil.

Puede consultar http://en.wikipedia.org/wiki/Conjunctive_normal_form, http://en.wikipedia.org/wiki/Disjunctive_normal_form, http://en.wikipedia.org/wiki/Binary_decision_diagram.

Fuente

2011-05-01 15:32:35 mcdowella

La creación de esos formularios que mencionas implica la creación de un mesa de verdad también. Por lo tanto, podría simplemente usar el hash de una forma normalizada (entradas y combinaciones ordenadas) de la tabla de verdad como la clave de almacenamiento en caché. Parece que la mejor manera es crear un hash "óptimo" para las consultas que cubren menos de 10 etiquetas y para las consultas con más etiquetas un algoritmo más simple pero no óptimo. – user733321

Debería poder obtener cualquiera de estas formas de manera puramente simbólica. Dadas dos expresiones en cualquiera de estas formas, puede calcular el resultado de combinar estas expresiones a través de Y u O, y el resultado será en la misma forma. Puedes hacer más o menos lo mismo con NOT. En algunos casos, el resultado será complejo, pero será posible. Para BDD debe haber bibliotecas para hacer esto - ver p. http://javabdd.sourceforge.net/apidocs/net/sf/javabdd/BDD.html. Entonces puedes construir una representación combinando las representaciones de variables individuales. – mcdowella

Pero no veo cómo esto evitaría la necesidad de un algoritmo NP-complete. – user733321

Puede convertir las consultas en forma normal conjuntiva (CNF). Es una representación canónica y simple de fórmulas booleanas que normalmente es la base para los solucionadores de SAT.

Lo más probable es que las consultas "grandes" vayan a tener muchas conjunciones (en lugar de muchas disyunciones), por lo que CNF debería funcionar bien.

Fuente

2011-05-01 21:05:27

¿Entonces construir un CNF de una 'no peor de las consultas de casos' sería menos complejo que NP? ¿Tiene una referencia sobre cómo implementar la conversión? El algoritmo común parece implicar tablas de verdad que son demasiado complejas. – user733321

Yo diría que sí. Ver http://en.wikipedia.org/wiki/Conjunctive_normal_form –

El algoritmo Quine-McCluskey debe lograr lo que busca. Es similar a los mapas de Karnaugh, pero es más fácil para implement in software.

Fuente

2011-05-01 21:17:19 blubb

Igual que con antti.huima. Es demasiado complejo para ser eficiente, ¿verdad? – user733321

normaliza la expresión booleana por razones de almacenamiento en caché. ¿hay una manera más eficiente que las tablas de verdad?

Respuesta

Cuestiones relacionadas