data structures - ¿Hay alguna estructura de datos probabilísticos que proporcione falsos negativos pero no falsos positivos?

data-structures hash

Question

Necesito una estructura de datos probabilísticos eficiente en el espacio para almacenar valores que ya he calculado. Para mí, el cálculo es barato, pero el espacio no lo es, así que si esta estructura de datos arroja un falso negativo, estoy de acuerdo con rehacer algún trabajo de vez en cuando, pero los falsos positivos son inaceptables. Entonces, lo que estoy buscando es una especie de opuesto a un filtro Bloom .

Answer 1

Para los negativos falsos, puede usar la tabla hash con pérdidas o un LRUCache. Es una estructura de datos con búsqueda rápida O (1) que solo arrojará falsos negativos. si pregunta si "He realizado la prueba X", le dirá "Sí, definitivamente tiene" o "No puedo recordar".

Pseudocódigo:

setup_test_table():
create test_table( some large number of entries )
clear each entry( test_table, NEVER )
return test_table
has_test_been_run_before( new_test_details, test_table ):
index = hash( test_details , test_table.length )
old_details = test_table[index].detail
// unconditionally overwrite old details with new details, LRU fashion.
// perhaps some other collision resolution technique might be better.
test_table[index].details = new_test_details
if ( old_details === test_details ) return YES
else if ( old_details === NEVER ) return NEVER
else return PERHAPS
main()
test_table = setup_test_table();
loop
test_details = generate_random_test()
status = has_test_been_run_before( test_details, test_table )
case status of
YES: do nothing;
NEVER: run test (test_details);
PERHAPS: if( rand()&1 ) run test (test_details);
next loop
end.

Del mismo modo Bloom filtro para falso positivo