가양 성을 제공하지만 가양 성을 제공하지는 확률 적 데이터 구조가 있습니까?

이미 계산 한 값을 저장하기 위해 공간 효율적인 확률 데이터 구조가 필요합니다. 나에게있어 계산은 저렴하지만 공간은 그렇지 않습니다. 따라서이 데이터 구조가 false negative를 반환하면 때때로 작업을 다시하고 괜찮습니다. 그러나 오 탐지는 용인 할 수 없습니다. 그래서 제가 찾고있는 것은 Bloom filter의 반대입니다.가양 성을 제공하지만 가양 성을 제공하지는 확률 적 데이터 구조가 있습니까?

출처

2012-11-07 pathikrit

참조

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.

마찬가지로 블룸 필터 : 링크 1 (http://stackoverflow.com/questions/635728/opposite-of-bloom-filter?rq = 1), [Link2] (http://cstheory.stackexchange.com/questions/6596/a-probabilistic-set-with-no-false-positives). – TaZ

false negative의 경우 손실이 많은 해시 테이블이나 LRUCache를 사용할 수 있습니다. 가짜 오 검지만을 제공하는 빠른 O (1) 검색을 사용하는 데이터 구조입니다. "X 검사를 실행 했습니까?"라는 질문을하면 "예, 확실합니다"또는 "기억이 안납니다"라고 표시됩니다.

의사 코드 : 또한 위양성

출처

2012-11-07 09:01:06

질문을 읽어보십시오. 블룸 필터는 내가 찾지 않는 필터입니다. – pathikrit

안녕하세요. Wrick, 내 답변이 수정되었습니다. 귀하의 목적에 부합하는지 알려주세요. –

가양 성을 제공하지만 가양 성을 제공하지는 확률 적 데이터 구조가 있습니까?

답변

관련 문제