FP 트리는 입력 데이터에 대한 확실한 설명입니다. 한 번에 하나의 트랜잭션 데이터 세트를 읽고 각 트랜잭션을 FP-트리의 경로에 대해 측정하여 조합됩니다. 여러 트랜잭션에는 여러 항목이 공통적으로 포함될 수 있으며 해당 경로는 겹칠 수 있습니다.
경로가 서로 겹칠수록 FP-트리 아키텍처를 사용하여 더 많은 압축을 구현할 수 있습니다. FP-tree의 크기가 주 메모리에 맞을 수 있다면 디스크에 저장된 데이터에 대해 반복적인 패스를 생성하지 않고 메모리의 아키텍처에서 직접 빈번한 항목 집합을 추출할 수 있습니다.
트리의 각 노드에는 주어진 경로에 매핑된 여러 트랜잭션을 표시하는 카운터와 함께 항목 레이블이 포함됩니다. 원래 FP-tree는 nulf 기호로 정의된 루트 노드만 포함합니다.
FP-tree는 다음과 같은 방법으로 계속됩니다 -
데이터 세트는 각 항목의 지원 개수를 결정하기 위해 한 번 검색됩니다. 흔하지 않은 아이템은 드랍되고, 빈번한 아이템은 지원 횟수를 줄이는 데 일정합니다.
알고리즘은 데이터에 대한 두 번째 패스를 생성하여 FP 트리를 만듭니다. 첫 번째 트랜잭션 {a, b}를 검토한 후 로 레이블이 지정된 노드와 b가 생성됩니다. 트랜잭션을 암호화하기 위해 null→a→b로 경로가 형성됩니다. 경로를 따라 있는 각 노드의 빈도 수는 1입니다.
두 번째 트랜잭션 {b, c, d}를 검토한 후 항목 b, c 및 d에 대해 새로운 노드 집합이 생성됩니다. 그런 다음 null→b→c→d 노드를 연결하여 트랜잭션을 정의하는 경로가 형성됩니다.
이 경로에 있는 각 노드는 빈도 수가 1과 동일합니다. 처음 두 트랜잭션에는 자주 항목인 b가 있지만 트랜잭션이 자주 접두사를 공유하지 않기 때문에 이들의 경로는 연결되지 않습니다.
세 번째 트랜잭션 {a, c, d, e}는 첫 번째 트랜잭션과 자주 접두사 항목(a)을 공유합니다. 따라서 세 번째 트랜잭션의 경로인 null→a→c→d→e는 첫 번째 트랜잭션의 경로인 nuII→a→b와 겹칩니다. 겹치는 경로로 인해 노드 o의 빈도 수는 2로 증가하는 반면 최근에 생성된 노드 c, d, e의 빈도 수는 1과 같습니다.
이 단계는 각 트랜잭션이 FP 트리에 제공된 경로 중 하나에 매핑될 때까지 계속됩니다. 장바구니 정보의 여러 거래가 더 많은 항목을 공유하기 때문에 FP 트리의 크기는 압축되지 않은 데이터의 크기보다 작습니다.