Class SimilarityIndex
This structure can be used to compute an approximation of the similarity
between two files. The index is used by
SimilarityRenameDetector
to compute scores
between files.
To save space in memory, this index uses a space efficient encoding which will not exceed 1 MiB per instance. The index starts out at a smaller size (closer to 2 KiB), but may grow as more distinct blocks within the scanned file are discovered.
- Since:
- 4.0
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
Thrown bycreate()
when file is too large. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate long
Total amount of bytes hashed into the structure, including \n.private int
private long[]
Pairings of content keys and counters.private int
idHash.length == 1 << idHashBits
.private int
Number of non-zero entries inidHash
.private static final int
Shift to apply before storing a key.private static final long
Maximum value of the count field, also mask to extract the count.static final SimilarityIndex.TableFullException
A specialSimilarityIndex.TableFullException
used in place of OutOfMemoryError. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) void
add
(int key, int cnt) private static long
common
(long[] srcHash, int srcIdx, long[] dstHash, int dstIdx) (package private) long
common
(SimilarityIndex dst) private static long
common
(SimilarityIndex src, SimilarityIndex dst) (package private) long
count
(int idx) private static long
countOf
(long v) static SimilarityIndex
create
(ObjectLoader obj) Create a new similarity index for the given object(package private) int
findIndex
(int key) private void
grow()
private static int
growAt
(int idHashBits) (package private) void
hash
(byte[] raw, int ptr, int end) (package private) void
hash
(InputStream in, long remaining, boolean text) (package private) void
hash
(ObjectLoader obj) private void
(package private) int
key
(int idx) private static int
keyOf
(long v) private int
packedIndex
(int idx) private static long
pair
(int key, long cnt) int
score
(SimilarityIndex dst, int maxScore) Compute the similarity score between this index and another.(package private) int
size()
private int
slot
(int key) (package private) void
sort()
Sort the internal table so it can be used for efficient scoring.
-
Field Details
-
TABLE_FULL_OUT_OF_MEMORY
A specialSimilarityIndex.TableFullException
used in place of OutOfMemoryError. -
KEY_SHIFT
private static final int KEY_SHIFTShift to apply before storing a key.Within the 64 bit table record space, we leave the highest bit unset so all values are positive. The lower 32 bits to count bytes.
- See Also:
-
MAX_COUNT
private static final long MAX_COUNTMaximum value of the count field, also mask to extract the count.- See Also:
-
hashedCnt
private long hashedCntTotal amount of bytes hashed into the structure, including \n. This is usually the size of the file minus number of CRLF encounters. -
idSize
private int idSizeNumber of non-zero entries inidHash
. -
idGrowAt
private int idGrowAt -
idHash
private long[] idHashPairings of content keys and counters.Slots in the table are actually two ints wedged into a single long. The upper 32 bits stores the content key, and the remaining lower bits stores the number of bytes associated with that key. Empty slots are denoted by 0, which cannot occur because the count cannot be 0. Values can only be positive, which we enforce during key addition.
-
idHashBits
private int idHashBitsidHash.length == 1 << idHashBits
.
-
-
Constructor Details
-
SimilarityIndex
SimilarityIndex()
-
-
Method Details
-
create
public static SimilarityIndex create(ObjectLoader obj) throws IOException, SimilarityIndex.TableFullException Create a new similarity index for the given object- Parameters:
obj
- the object to hash- Returns:
- similarity index for this object
- Throws:
IOException
- file contents cannot be read from the repository.SimilarityIndex.TableFullException
- object hashing overflowed the storage capacity of the SimilarityIndex.
-
hash
void hash(ObjectLoader obj) throws MissingObjectException, IOException, SimilarityIndex.TableFullException -
hashLargeObject
private void hashLargeObject(ObjectLoader obj) throws IOException, SimilarityIndex.TableFullException -
hash
-
hash
void hash(InputStream in, long remaining, boolean text) throws IOException, SimilarityIndex.TableFullException -
sort
void sort()Sort the internal table so it can be used for efficient scoring.Once sorted, additional lines/blocks cannot be added to the index.
-
score
Compute the similarity score between this index and another.A region of a file is defined as a line in a text file or a fixed-size block in a binary file. To prepare an index, each region in the file is hashed; the values and counts of hashes are retained in a sorted table. Define the similarity fraction F as the count of matching regions between the two files divided between the maximum count of regions in either file. The similarity score is F multiplied by the maxScore constant, yielding a range [0, maxScore]. It is defined as maxScore for the degenerate case of two empty files.
The similarity score is symmetrical; i.e. a.score(b) == b.score(a).
- Parameters:
dst
- the other indexmaxScore
- the score representing a 100% match- Returns:
- the similarity score
-
common
-
common
-
common
private static long common(long[] srcHash, int srcIdx, long[] dstHash, int dstIdx) -
size
int size() -
key
int key(int idx) -
count
long count(int idx) -
findIndex
int findIndex(int key) -
packedIndex
private int packedIndex(int idx) -
add
-
pair
-
slot
private int slot(int key) -
growAt
private static int growAt(int idHashBits) -
grow
-
keyOf
private static int keyOf(long v) -
countOf
private static long countOf(long v)
-