IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

1

PAPER

NCDSearch: Sliding Window-Based Code Clone Search Using
Lempel-Ziv Jaccard DistanceTakashi ISHIO†a) , Member, Naoto MAEDA†† , Kensuke SHIBUYA†† , Kenho IWAMOTO†† , Nonmembers,
and Katsuro INOUE††† , Fellow

SUMMARY Software developers may write a number of similar sourcecode fragments including the same mistake in software products. To remove
such faulty code fragments, developers inspect code clones if they found a
bug in their code. While various code clone detection methods have been
proposed to identify clones of either code blocks or functions, those tools
do not always ﬁt the code inspection task because a faulty code fragment
may be much smaller than code blocks, e.g. a single line of code. To enable
developers to search code clones of such a small faulty code fragment ina large-scale software product, we propose a method using Lempel-Ziv
Jaccard Distance, which is an approximation of Normalized Compression
Distance. We conducted an experiment using an existing research dataset
and a user survey in a company. The result shows our method eﬃciently
reports cloned faulty code fragments and the performance is acceptable forsoftware developers.
key words: Source code search, Normalized compression distance

1. Introduction
Software developers may write a number of similar sourcecode fragments including the same mistake in software products [1]–[3]. To ﬁx the same bug in multiple locations at
once, code clone detection tools have been employed in industry [4]. When developers identiﬁed a faulty source codefragment, they execute a code clone detection tool and investigate code clones of the faulty code fragment.
To eﬃciently perform such a bug-ﬁxing task, softwaredevelopers require an eﬃcient code clone detection tool thattakes as input a query code fragment and report its code
clones in a software product. A tool specialized for the task
is CBCD (Cloned Buggy Code Detector) [5]. The tool translates a query code fragment into a graph representation basedon a program dependence graph [6], and then detects isomorphic subgraphs in the entire source code. Although thetool eﬀectively detects faulty code clones, the tool requires
a program dependence graph for a target program. While
GrammaTech CodeSurfer is available for C language, it isdiﬃcult for developers to prepare similar tools for various
programming languages (e.g. Java and C#) used for theirsoftware products.
As a programming langauge-independent search tool,
Manuscript received January 1, 2015.
Manuscript revised January 1, 2015.
† The author is with Nara Institute of Science and Technology,
Japan.
†† The author is with NEC Corporation, Japan.
††† The author is with Osaka University, Japan.
a) E-mail: ishio@is.naist.jp
DOI: 10.1587/transinf.E0.D.1

we have developed a tool named NCDSearch† . The tool
uses Normalized Compression Distance [7] for source code
similarity because the distance is resilient to content changes
such as renaming and reordering [8]–[10]. Our previous
work [11] shows that NCDSearch eﬀectively identiﬁes faulty
code clones for a query code fragment. On the other hand,
the tool takes around 10 minutes per query on average toscan a large software product like Linux kernel comprisingmillions of lines of code. The performance is acceptable forsome developers who have used existing code clone detection
tools; however, the tool is still slow for daily bug-ﬁxing tasks
in industry.
In this study, we propose an eﬃcient code clone searchmethod using Lempel-Ziv Jaccard Distance (LZJD) [12],[13]. Our method is a sliding window algorithm that takes
as input a query code fragment and source code. Our key
component is an eﬃcient comparison between the query anda code fragment extracted by a sliding window; while theoriginal deﬁnition of LZJD [12] is to compare a pair ofﬁxed-size strings, we deﬁne an algorithm that compares aquery with multiple sub-strings of a code fragment at once.
To further improve the eﬃciency, we also introduce a ﬁleselection step that quickly decides whether a ﬁle should be
investigated or not.
We implemented the algorithm as a new version ofNCDSearch and evaluated the performance using the CBCD
benchmark [14]. The result shows that the new version is
20x faster than the previous version while keeping accuracy.
The tool is deployed in NEC Corporation that employs morethan ten thousand developers. In response to our tool announcement, 101 users have tried the tool. We conducteda user survey and received 15 responses from those users;
73% of them responded that they will continue to use the tool.
Since the previous version has not been widely accepted in
the company, the performance improvement is signiﬁcant fordevelopers.
The remainder of this paper is organized as follows:
Section 2 explains the research background. Section 3 describes the proposed method. Section 4 shows the result ofour performance evaluation using a benchmark dataset. Section 5 describes our user evaluation. Section 6 summarizes
the results and future directions of the study.

† https://github.com/takashi-ishio/NCDSearch

Copyright © 200x The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

2

Code change 1:- perm_fmgr_info(typeStruct->typoutput,&(prodesc->arg_out_func[i]));+ fmgr_info_cxt(typeStruct->typoutput,+&(prodesc->arg_out_func[i]),+proc_cxt);
Code change 2:- perm_fmgr_info(typeStruct->typinput,&(prodesc->result_in_func));+ fmgr_info_cxt(typeStruct->typinput,+&(prodesc->result_in_func),+
proc_cxt);
Fig. 1 A pair of similar code changes performed in PostgreSQL [14].
Both changes have been performed in commit 6f7c0ea32.

2. Background
2.1 Code Clone Detection
Duplicated source code, also known as code clones, is considered as a code smell [15]. To support software maintenance activities, various code clone detection tools have been
proposed [16]. Most of the code clone detection tools aredesigned to eﬃciently detect large code clones, e.g. blocklevel and function-level code clones, in software products.
For example, CCFinderX [17] reports code clones that are
longer than 50 tokens by default. NiCad [18] detects only
cloned functions or code blocks. On the other hand, a bug
ﬁx may be a small code fragment, e.g. a single line ofcode [19]. Fig.1 is an example pair of code clones of such asmall change. When the code change 1 has been performed,
we would like to detect the source code location for codechange 2 (the lines of perm_fmgr_info function call) as acode clone. However, the code clones are ignored by thedetection tools.
CBCD [5] has been proposed to detect code clones ofa small faulty code fragment by comparing context information of code fragments using program dependence analysis [6]. While the tool is very eﬀective for our purpose,
it is hard to prepare program dependence analysis components for various programming languages used in software
companies.
ReDeBug [20], Vuddy [21], and CLORIFI [22] havebeen proposed to eﬃciently apply security patches to software products. They take a bug ﬁx patch as input and reportsource code fragments where the patch has not been appliedyet. Although the usage scenario is close to our motivation, those tools use unsuitable heuritics to the bug-ﬁxng
task. For example, ReDeBug detects only source ﬁles including the entire patch content. Vuddy detects code clones
of known vulnerable functions that are syntactically identical
except for identiﬁer names. Their conservative analyses do
not detect modiﬁed code clones. CLORIFI introduces constraints specialized for security patches that are unavailable

for general bugs.
Balachandran [23] proposed a code search algorithm
using a structural similarity of abstract syntax trees. It enables a user to search code examples using syntactic patterns
ignoring semantic diﬀerences such as data types and function
names in a query code fragment. Our method uses a textual
similarity, since clones of a buggy code fragment likely use
similar functions and variables.
Siamese [24] is a code clone search tool that takes as
input a query code fragment and detects its clones in a large
code base such as GitHub projects. To eﬃciently searcha large code base, the tool builds an index database for thetarget code base in prior to queries. However, such a databaseis redundant for a bug-ﬁxing task because developers needto search code clones only once for a particular version ofa product. Our method simply scans the entire source codeon-the-ﬂy.
CCGrep [25] is a code clone search tool supporting
meta-tokens that are similar to regular expressions but specialized for source code. While it enables developers tospecify exact code patterns they want to detect, specifying
such patterns may be time-consuming for developers because
they have to understand code clone patterns at ﬁrst.
2.2

NCDSearch

Our previous work [11] implements a code clone searchtool named NCDSearch. The tool takes as input a querycode fragment 𝑞 and source code. The tool extracts sourcecode fragments of diﬀerent sizes using a sliding window andcompare them with the query.
The tool uses Normalized Compression Distance(NCD) for source code similarity. Given a query code fragment 𝑞 and a source code fragment 𝑠, the distance is deﬁned
as follows:
𝑁𝐶𝐷 (𝑞, 𝑠) =𝐶 (𝑞𝑠) − 𝑚𝑖𝑛{𝐶 (𝑞), 𝐶 (𝑠)}𝑚𝑎𝑥{𝐶 (𝑞), 𝐶 (𝑠)}where 𝐶 (𝑞𝑠) denotes the compressed size of the concatenation of 𝑞 and 𝑠, 𝐶 (𝑞) denotes the compressed size of𝑞, and 𝐶 (𝑠) denotes the compressed size of 𝑠. The distance regards two source code fragments as similar if they
are highly compressed by a data compression algorithm. In
implementation, we use Deﬂate algorithm (i.e., gzip) fordata compression. We use experimentally determined window sizes: {0.80|𝑞|, 0.85|𝑞|, 0.90|𝑞|, 0.95|𝑞|, |𝑞|, 1.05|𝑞|,
1.10|𝑞|, 1.15|𝑞|, 1.20|𝑞|}, where |𝑞| is the number of tokens
in the query code fragment.
A limitation of the approach is the computational cost.
As we cannot predict the result of a data compression, thetool has to separately calculate NCD values for each sourcecode fragment, even though diﬀerent sliding windows extract
very similar code fragments. As a result, NCDSearch takes
around 10 minutes per query to scan a large software productlike Linux kernel comprising millions of lines of code. The
performance is unsatisfactory for daily bug-ﬁxing tasks ofdevelopers.

ISHIO et al.: NCDSEARCH: SLIDING WINDOW-BASED CODE CLONE SEARCH USING LEMPEL-ZIV JACCARD DISTANCE

3

Algorithm 1 LZSet Extraction [13]3. Code Clone Search using LZJD
Our method identiﬁes code clones of a query code fragment 𝑞
in a set of source ﬁles 𝐹. Our method comprises three steps:
ﬁle selection, code search, and ﬁltering. The ﬁle selection
step selects a subset of source ﬁles that likely include code
clones of the query code fragment. The code search stepscans the selected ﬁles using a sliding window and compare
code fragments with the query. Finally, the ﬁltering step
removes redundant reports.
To support various programming languages used inindustry (e.g. C, Java, COBOL, JavaScript, and Python),our method is designed as language independent except for
lexical analysis. Our method requires only a lexer for the
programming language of 𝑞 and 𝐹. any programming language can be handled if the lexer can translate the queryand ﬁles into sequences of tokens excluding comments andwhite space. Our method translates the token sequences into
byte strings by concatenating null-terminated strings. For
example, a source code fragment “int i=0;” is tokenized
and then translated into a byte sequence “int␣i␣=␣0␣;␣”,where “␣” is the null character. As our method utilizes textual similarity of source code, visual programming languages
are unsupported by the method.
3.1 File Selection
The ﬁle selection step checks if each source ﬁle 𝑓 ∈ 𝐹
likely includes the query code fragment 𝑞. If the ﬁle likely
includes the query, we analyze the ﬁle in the code search
step. Otherwise, we skip the code search step for the ﬁle.
This step is inspired by ReDeBug [20] that eﬃciently detects
unpatched ﬁles using a simple condition: N-grams( 𝑝) ⊆N-grams( 𝑓 ) that compares N-grams of tokens extracted froma patch 𝑝 and a ﬁle 𝑓 . We use a similar but relaxed condition
because code clones may be diﬀerent from the query code.
We deﬁne an Overlap coeﬃcient 𝑂𝑣𝑒𝑟𝑙𝑎 𝑝 𝑁 (𝑞, 𝑓 ) that
becomes higher if a greater amount of the query 𝑞 is included
in 𝑓 :
𝑂𝑣𝑒𝑟𝑙𝑎 𝑝 𝑁 (𝑞, 𝑓 ) =|N-grams(𝑞) ∩ N-grams( 𝑓 )||N-grams(𝑞)|where N-grams(𝑥) is a multiset of N-grams of charactersin a byte string representation of 𝑥. We use N-grams ofcharacters instead of tokens because a query can be a single
line of code; N-grams of tokens may be too small to becompared.
Using the Overlap coeﬃcient, we select a subset of ﬁles𝐹𝑠 from source ﬁles 𝐹 as follows:
𝐹𝑠 = { 𝑓 ∈ 𝐹 | 𝑂𝑣𝑒𝑟𝑙𝑎 𝑝 𝑁 (𝑞, 𝑓 ) ≥ 𝜃 𝑓 }where 𝜃 𝑓 is a threshold for the ﬁle selection. The selectedﬁles 𝐹𝑠 are analyzed by the code search step. In our implementation, we experimentally decided the parameters: 𝑁 = 5
and 𝜃 𝑓 = 0.5.

Inputs𝑏: A byte array representation of a query.
Outputs
𝐿𝑍 𝑆𝑒𝑡 (𝑏): A Lempel-Ziv Set for the byte string 𝑏.
1: Initialize 𝑆 ← 𝜙
2: 𝑠𝑡 𝑎𝑟 𝑡 ← 0
3: 𝑒𝑛𝑑 ← 1
4: while 𝑒𝑛𝑑 ≤ 𝑙𝑒𝑛𝑔𝑡 ℎ (𝑏) do
5:𝑏𝑠 ← 𝑏 [𝑠𝑡 𝑎𝑟 𝑡 : 𝑒𝑛𝑑 ]6:
if 𝑏𝑠 ∉ 𝑆 then7:
𝑆 ← 𝑆 ∪ {𝑏𝑠 }8:𝑠𝑡 𝑎𝑟 𝑡 ← 𝑒𝑛𝑑
9:
end if10:𝑒𝑛𝑑 ← 𝑒𝑛𝑑 + 1
11: end while
12: return 𝑆 as 𝐿𝑍 𝑆𝑒𝑡 (𝑏)𝐿𝑍 𝑆𝑒𝑡 (Code Change 1) = { p|e|r|m|_|f|mg|r_|i|n|fo|␣|(|␣t|y|pe|S|t|ru|c|t␣|-|>|␣ty|po |u|tp |ut |␣,|␣&|␣(|␣p|ro|d|es|c␣|->|␣a |rg |_o |ut_|fu |nc |␣[ |␣i |␣]|␣)|␣)␣|; }𝐿𝑍 𝑆𝑒𝑡 (Code Change 2) = { p|e|r|m|_|f|mg|r_|i|n|fo|␣|(|␣t|y|pe|S|t|ru|c|t␣|-|>|␣ty|pi |np |u|t␣,|␣&|␣(|␣p|ro|d|es|c␣|->|␣r |esu |l |t_|in |_f |un |c␣)|␣)|␣; }|𝐿𝑍 𝑆𝑒𝑡 (Code Change 1) | = 49
|𝐿𝑍 𝑆𝑒𝑡 (Code Change 2) | = 46
|𝐿𝑍 𝑆𝑒𝑡 (Code Change 1) ∩ 𝐿𝑍 𝑆𝑒𝑡 (Code Change 2 | = 34
𝐿𝑍 𝐽 𝐷 (Code Change 1, Code Change 2) = 0.443
Fig. 2 LZSet for two code changes (removed source code indicated by“-”) in Fig.1 and their LZJD. Items in bold italic text are unique elements
to the LZSet.

3.2

Code Search

The code search step identiﬁes code clones in each ﬁle𝑓 ∈ 𝐹𝑠 selected by the previous step. In this step, we use asliding window whose size is 𝑤 tokens. For each line in theﬁle 𝑓 , we extract a code fragment 𝑐 that starts from the line.
The ﬁrst 𝑘 tokens of the code fragment 𝑐 is denoted by 𝑐 𝑘(1 ≤ 𝑘 ≤ 𝑤). We detect 𝑐 𝑘 as a code clone if it is similar
to 𝑞. If there exists multiple candidates, we select only themost similar code fragment.
For source code similarity between a query 𝑞 anda string 𝑐 𝑘 , we adopt Lempel-Ziv Jaccard Distance(LZJD) [12] deﬁned as follows:
𝐿𝑍 𝐽 𝐷 (𝑞, 𝑐 𝑘 ) = 1 −|𝐿𝑍 𝑆𝑒𝑡 (𝑞) ∩ 𝐿𝑍 𝑆𝑒𝑡 (𝑐 𝑘 )||𝐿𝑍 𝑆𝑒𝑡 (𝑞) ∪ 𝐿𝑍 𝑆𝑒𝑡 (𝑐 𝑘 )|where 𝐿𝑍 𝑆𝑒𝑡 (𝑞) and 𝐿𝑍 𝑆𝑒𝑡 (𝑐 𝑘 ) are simpliﬁed Lempel-Ziv
Sets of the byte strings of 𝑞 and 𝑐 𝑘 , respectively.
Algorithm 1 shows the algorithm to calculate 𝐿𝑍 𝑆𝑒𝑡 (𝑏)for a byte string 𝑏 deﬁned in [12]. It splits a byte string 𝑏 intosub-strings, using a simpliﬁed version of the Lempel-Ziv 78
algorithm (LZ78) [26]† . 𝐿𝑍 𝑆𝑒𝑡 (𝑏) represents a dynamic† The LZJD paper [12] says that the authors use the LZ77 algorithm [27]. However, the deﬁnition of LZSet is closer to the LZ78
algorithm in our understanding.

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

4Algorithm 2 LZJD-based Comparison

Algorithm 3 Code Search

Inputs𝑏: A byte array of the source code in the sliding window.
𝑤: A window size represented by the number of tokens
𝑝𝑜𝑠 [𝑖 ] (1 ≤ 𝑘 ≤ 𝑤): The position of the last byte of 𝑘-th token in 𝑏
𝐿𝑍 𝑆𝑒𝑡 (𝑞): LZSet for the query
Outputs
𝑘𝑏𝑒𝑠𝑡 : The number of tokens that the most similar to the query𝑙𝑧 𝑗 𝑑𝑏𝑒𝑠𝑡 : 𝐿𝑍 𝐽 𝐷 (𝑞, 𝑐𝑘𝑏𝑒𝑠𝑡 )1: Initialize 𝑆 ← 𝜙
2: 𝑠𝑡 𝑎𝑟 𝑡 ← 0
3: 𝑒𝑛𝑑 ← 1
4: 𝑖𝑛𝑡𝑒𝑟 𝑠𝑒𝑐𝑡𝑖𝑜𝑛 ← 0
5: 𝑙𝑧 𝑗 𝑑𝑏𝑒𝑠𝑡 ← ∞6: for 𝑘 = 1 to 𝑤 do
7:
while 𝑒𝑛𝑑 ≤ 𝑝𝑜𝑠 [𝑘 ] do8:𝑏𝑠 ← 𝑏 [𝑠𝑡 𝑎𝑟 𝑡 : 𝑒𝑛𝑑 ]9:
if 𝑏𝑠 ∉ 𝑆 then10:
𝑆 ← 𝑆 ∪ {𝑏𝑠 }11:𝑠𝑡 𝑎𝑟 𝑡 ← 𝑒𝑛𝑑
12:
if 𝑏𝑠 ∈ 𝐿𝑍 𝑆𝑒𝑡 (𝑞) then13:
𝑖𝑛𝑡𝑒𝑟 𝑠𝑒𝑐𝑡𝑖𝑜𝑛 ← 𝑖𝑛𝑡𝑒𝑟 𝑠𝑒𝑐𝑡𝑖𝑜𝑛 + 1
14:
end if15:
end if16:
𝑒𝑛𝑑 ← 𝑒𝑛𝑑 + 1
17:
end while𝑖𝑛𝑡𝑒𝑟 𝑠𝑒𝑐𝑡𝑖𝑜𝑛18:
𝑙𝑧 𝑗 𝑑 ← 1 − |𝐿𝑍 𝑆𝑒𝑡 (𝑞)|+|𝑆|−𝑖𝑛𝑡𝑒𝑟 𝑠𝑒𝑐𝑡𝑖𝑜𝑛
19:
if 𝑙𝑧 𝑗 𝑑 < 𝑙𝑧 𝑗 𝑑𝑏𝑒𝑠𝑡 then20:
𝑘𝑏𝑒𝑠𝑡 ← 𝑘21:
𝑙𝑧 𝑗 𝑑𝑏𝑒𝑠𝑡 ← 𝑙𝑧 𝑗 𝑑
22:
end if
23: end for
24: return 𝑘𝑏𝑒𝑠𝑡 and 𝑙𝑧 𝑗 𝑑𝑏𝑒𝑠𝑡

Inputs𝑞: A query
𝑤: A window size represented by the number of tokens
𝜃𝑙 : Threshold for code clones
𝑓 : A target ﬁle that passed ﬁle-level search
Outputs
𝐶: Code clones detected in the ﬁle 𝑓
1: Initialize 𝐶 ← 𝜙
2: Translate 𝑞 into 𝐿𝑍 𝑆𝑒𝑡 (𝑞)3: for each line 𝑙 in 𝑓 do
4:𝑏 ← A byte string for 𝑤 tokens that start from the line 𝑙5:𝑝𝑜𝑠 ← token positions in 𝑏
6:
𝑘𝑏𝑒𝑠𝑡 , 𝑙𝑧 𝑗 𝑑𝑏𝑒𝑠𝑡 ← Algorithm 2 (𝑏, 𝑤, 𝑝𝑜𝑠, 𝐿𝑍 𝑆𝑒𝑡 (𝑞))7:
if 𝑙𝑧 𝑗 𝑑𝑏𝑒𝑠𝑡 < 𝜃𝑙 then8:
𝐶 ← 𝐶 ∪ {𝐶𝑙𝑜𝑛𝑒 ( 𝑓 , 𝑙, 𝑘𝑏𝑒𝑠𝑡 , 𝑙𝑧 𝑗 𝑑𝑏𝑒𝑠𝑡 ) }9:
end if
10: end for
11: return 𝐶

dictionary for compressing the byte sequence 𝑏 in the LZ78
algorithm. Conceptually, LZJD compares dictionaries fordata compression instead of the actual data compression
results. Fig.2 shows an example pair of LZSets for codechanges in Fig.1 and their LZJD.
While we use Algorithm 1 to obtain 𝐿𝑍 𝑆𝑒𝑡 (𝑞),we deﬁne another algorithm to eﬃciently compare
𝐿𝑍 𝑆𝑒𝑡 (𝑞) with 𝐿𝑍 𝑆𝑒𝑡 (𝑐 𝑘 ) extracted by the sliding window.
Our key insight is: Algorithm 1 constructs
𝐿𝑍 𝑆𝑒𝑡 (𝑏) by linearly scanning a byte string 𝑏. Hence,
when we calculate 𝐿𝑍 𝑆𝑒𝑡 (𝑐 𝑤 ), the algorithm produces
𝐿𝑍 𝑆𝑒𝑡 (𝑐 1 ), 𝐿𝑍 𝑆𝑒𝑡 (𝑐 2 ), · · · , 𝐿𝑍 𝑆𝑒𝑡 (𝑐 𝑤−1 ) as intermediate
results. We compare 𝐿𝑍 𝑆𝑒𝑡 (𝑞) with those intermediate results to identify the most similar sub-string 𝑐 𝑘 .
Algorithm 2 shows our source code comparison function. It takes as input a byte string 𝑏 including 𝑤 tokens
selected by the sliding window. For each 𝑘-th token in thecode fragment, the algorithm updates 𝑆 at lines 7–17. A variable 𝑖𝑛𝑡𝑒𝑟 𝑠𝑒𝑐𝑡𝑖𝑜𝑛 keeps the number of common elements in
𝐿𝑍 𝑆𝑒𝑡 (𝑞) and 𝑆. At line 18, the algorithm calculates LZJD
between the query 𝑞 and 𝑐 𝑘 . The entire algorithm reports
the most similar sub-string 𝑐 𝑘 in the sliding window.
Using Algorithm 2 as a subroutine, we deﬁne our code
search step as shown in Algorithm 3. The code search takes
an additional parameter 𝑤 that speciﬁes the size of a sliding
window. The sliding window moves line by line within theﬁle 𝑓 . For each line, the algorithm extracts a code fragment𝑏 including 𝑤 tokens, and then calls Algorithm 2 to identify asub-string 𝑐 𝑘𝑏𝑒𝑠𝑡 that is the most similar to 𝑞. If the 𝑙𝑧 𝑗 𝑑 𝑏𝑒𝑠𝑡value is less than a threshold 𝜃 𝑙 , the sub-string from the line
is detected as a code clone.
The size of the sliding window is decided by the number of tokens in the query ignoring comments and whitespace. We experimentally determined the window size
𝑤 = ⌊1.20|𝑞|⌋, where |𝑞| is the number of tokens in thequery 𝑞. This is the maximum window size we have used in
our previous work [11].
The time complexity of this code search step is 𝑂 (𝑤𝑛),where 𝑛 is the total size of source code. As a sliding window
includes 𝑤 tokens, each token in a ﬁle is processed at most 𝑤
times even if a ﬁle contains one token per line. To reduce thecomputation time, Algorithm 2 can be executed in parallel
for multiple lines or ﬁles because the algorithm have no side
eﬀect on the global data structure such as 𝐿𝑍 𝑆𝑒𝑡 (𝑞).
The space complexity is 𝑂 (𝑛). The space is required
to keep tokens and its byte string representation on memory.
Since the data structure for a ﬁle can be discarded after asearch on the ﬁle, the actual memory footprint depends onthe maximum size of individual ﬁles.
3.3

Filtering

The code search step may detect a number of overlapping
code fragments as code clones. To exclude such redundant
reports, we choose the most similar code fragment (i.e. thathas the shortest distance) from the overlapping clones. Iftied, we choose the shortest code fragment.
After the ﬁltering, four attributes are reported for eachclone: the ﬁle name, the ﬁrst line number, the length, andthe distance from a query. A user can easily sort the reported
code clones by the locations and distances.

ISHIO et al.: NCDSEARCH: SLIDING WINDOW-BASED CODE CLONE SEARCH USING LEMPEL-ZIV JACCARD DISTANCE

5
Table 1

Cloned Buggy Code Detector Dataset [14]𝑇 𝑃(𝐹, 𝐶) =#Queries|𝑞 |(Med.)#Bugs#Files(Med.)

LOC(Med.)

PostgreSQL
Git
Linux

14
5
34

15
19
17.5

39
8
41

1,058
261
22,181

277,959
67,0286,931,715

Total

53

1208

88

792,432

241,074,652

Projects

4. Benchmark-based Evaluation• Most of queries include a few lines of code. The median is 2 lines of code (17 tokens). The longest query
includes 14 lines (93 tokens).
• In case of 42 bugs, a single buggy clone is included insource code. The maximum number of buggy clones
of a query is 18.
• In case of 25 bugs, the cloned fragments are type-1
clones (i.e. exact copies). The other clones have some
diﬀerences from the query code fragments.
Table 1 shows the numbers of queries for each project, themedian number of tokens of queries, and the median sizeof C/C++ ﬁles in the analyzed versions of the projects. Thelines of code exclude comment and empty lines. Since thedataset written in [14] included some errors (e.g. incorrectline numbers and commit ids), we manually examined thecommit history of three programs and updated the dataset.
The full content is included in the NCDSearch source code
repository† .
For each query in the benchmark, we evaluate a list ofreported code clones 𝐶 = {𝑐 1 , 𝑐 2 , · · · , 𝑐 |𝐶 | } sorted by theirsimilarity (distance) values. We classify the clones in 𝐶 intotrue positives and false positives by comparing with faulty
code clones 𝐹 in the benchmark. We consider a reported
code clone 𝑐 𝑖 ∈ 𝐶 detects a faulty code clone 𝑓 ∈ 𝐹 if 𝑐 𝑖includes at least a single line of 𝑓 . Since multiple code clones
in 𝐶 may detect the same faulty code clone 𝑓 , we regard
only the most similar (top-ranked) code clone detecting 𝑓 asa true positive corresponding to 𝑓 . More formally, a set oftrue positive clones 𝑇 𝑃(𝐹, 𝐶) is deﬁned as follows.
† https://github.com/takashi-ishio/NCDSearch/#e

valuation-dataset𝑡 𝑝( 𝑓 , 𝐶)𝑓 ∈𝐹𝑡 𝑝( 𝑓 , 𝐶) = {𝑐 𝑖 ∈ 𝐶 | 𝑜𝑣𝑒𝑟𝑙𝑎 𝑝( 𝑓 , 𝑐 𝑖 )∧ ∀𝑘 (1 ≤ 𝑘 < 𝑖). ¬𝑜𝑣𝑒𝑟𝑙𝑎 𝑝( 𝑓 , 𝑐 𝑘 )}where 𝑜𝑣𝑒𝑟𝑙𝑎 𝑝( 𝑓 , 𝑐) is a boolean function representing
whether a line of 𝑓 is included in 𝑐 or not. In the deﬁnition,𝑡 𝑝( 𝑓 , 𝐶) selects at most one code clone 𝑐 𝑖 corresponding to𝑓 . If 𝑐 𝑖 includes multiple faulty code clones, the same 𝑐 𝑖 isselected for those code clones. A set of faulty code clones
detected by the true positives is represented as follows.
𝐷𝑒𝑡𝑒𝑐𝑡𝑒𝑑 (𝐹, 𝐶) = { 𝑓 ∈ 𝐹 | ∃𝑐 ∈ 𝐶. 𝑜𝑣𝑒𝑟𝑙𝑎 𝑝( 𝑓 , 𝑐)}

4.1 Benchmark
To evaluate the accuracy and eﬃciency of the proposed
method, we use a benchmark dataset for the CBCD tool [14].
The dataset includes 53 cloned bugs extracted from issue
tracking systems of three OSS projects: PostgreSQL, Git,and Linux. The main programming language of the projects
is C/C++. Each bug item comprises a query code fragment,
a commit ID of a product version, and a list of faulty code
clones in the version. Each faulty code clone is represented
by a ﬁle name and the ﬁrst and last line numbers in the ﬁle.
The queries have the following properties:∪

Using 𝑇 𝑃(𝐹, 𝐶) and 𝐷𝑒𝑡𝑒𝑐𝑡𝑒𝑑 (𝐹, 𝐶), we calculate precision and recall of the reported clones as follows.
|𝑇 𝑃(𝐹, 𝐶)||𝐶 ||𝐷𝑒𝑡𝑒𝑐𝑡𝑒𝑑 (𝐹, 𝐶)|
𝑅𝑒𝑐𝑎𝑙𝑙 (𝐹, 𝐶) =|𝐹 |𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛(𝐹, 𝐶) =In addition to precision and recall, we use mean average
precision (MAP) to evaluate the eﬀectiveness of LZJD as aranking mechanism for 𝐶. MAP is the mean of average
precision for all queries. Average precision is the mean of
the precision scores obtained after each relevant document isretrieved, using zero as the precision for relevant documentsthat are not retrieved [28]. In our study, higher average
precision values represent that true positive clones appear
earlier in the list. Average precision is calculated as follows.
1 ∑𝐴𝑃(𝐹, 𝐶) =𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛(𝐹, 𝐶𝑠 ( 𝑓 ))|𝐹 | 𝑓 ∈𝐹{{𝑐 𝑘 ∈ 𝐶 | 1 ≤ 𝑘 ≤ 𝑖 } if 𝑡 𝑝( 𝑓 , 𝐶) = {𝑐 𝑖 }𝐶𝑠 ( 𝑓 ) =𝜙otherwise𝐶𝑠 ( 𝑓 ) represents a sub-list of code clones 𝑐 1 , · · · , 𝑐 𝑖 suchthat 𝑐 𝑖 is the true positive including 𝑓 . For example, suppose
there exists two faulty code clones (𝐹 = { 𝑓1 , 𝑓2 }) and our
method reports three code clones (𝐶 = {𝑐 1 , 𝑐 2 , 𝑐 3 }). If 𝑐 1
and 𝑐 3 respectively include 𝑓1 and 𝑓2 (i.e., 𝑡 𝑝( 𝑓1 , 𝐶) = {𝑐 1 }and 𝑡 𝑝( 𝑓2 , 𝐶) = {𝑐 3 }), we obtain 𝐶𝑠 ( 𝑓1 ) = {𝑐 1 }, 𝐶𝑠 ( 𝑓2 ) ={𝑐 1 , 𝑐 2 , 𝑐 3 }. The average precision is 𝐴𝑃(𝐹, 𝐶) = 12 ( 11 + 23 ) =0.833.
4.2

Tool Conﬁgurations

We have implemented the proposed method as a new versionof NCDSearch (v0.3.5). We have executed the proposed
method using ﬁve conﬁgurations as follows:
P1 The proposed method with 𝜃 𝑙 = 0.5
P2 The proposed method with 𝜃 𝑙 = 0.6
P3 The code search with 𝜃 𝑙 = 0.5 without using the ﬁleselection step
P4 The code search with 𝜃 𝑙 = 0.6 without using the ﬁleselection step

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

6
Table 2ID

Conﬁguration#Reported
Med.
Total

P1
P2
P3
P4
P5

File Selection + LZJD 𝑡 ℎ = 0.5
File Selection + LZJD 𝑡 ℎ = 0.6
LZJD 𝑡 ℎ = 0.5
LZJD 𝑡 ℎ = 0.6
File Selection + Baseline 1

8
49
11
112
20

Performance of the tools (53 queries).
#Detected
Med. Total

2570
9124
3693
48841
4914

B1
NCD with Deﬂate 𝑡 ℎ = 0.5 [11]
22
8068
B2
Normalized Levenshtein 𝑡 ℎ = 0.5
363 711270
B3
CCFinderX (50 tokens)
1
55
B4
CCFinderX ( |𝑞 | tokens)
6 367021
B5
NiCad (Block, 3 lines)
019
B6
NiCad (Block, 10 lines)
018
B7
NiCad (Functions, 3 lines)
021
B8
NiCad (Functions, 10 lines)
020
B9CBCD (Estimated) [5], [14]18408
* Multiple faulty code clones are detected as a single code clone.

Recall
Med.
Total

MAP

Time
Med. (sec.) Total

1
1
1
1
1

82
88
82
88
88

0.158
0.143
0.027
0.013
0.083

0.032
0.010
0.022
0.002
0.018

1.000
1.000
1.000
1.000
1.000

0.932
1.000
0.932
1.000
1.000

0.749
0.753
0.749
0.752
0.757

34
36
44
46
31

26min 38sec
28min 12sec
41min 30sec
43min 11sec
52min 39sec

1
1
1
1
0
0
0
0
1

88
87
64*
61
13
12
14
13
82

0.053
0.004
0.500
0.023
0.000
0.000
0.000
0.000
1.000

0.011
<0.001
0.782<0.001
0.684
0.667
0.667
0.650
0.010

1.000
1.000
1.000
1.000
0.000
0.000
0.000
0.000
1.000

1.000
0.989
0.750
0.753
0.148
0.136
0.160
0.148
0.932

0.757
0.754
N/A
N/A
N/A
N/A
N/A
N/A
N/A

618
65
1642
539
1906
2149
2479
2462
N/A

12h 59min
2h 52min21h 30min
6h 22min24h 53min27h24min35h 53min
35h 14min
N/A

P5 The ﬁle selection step combined with the normalized
compression distance (𝑡ℎ = 0.5)
P1 and P2 use the full version of the proposed method with
diﬀerent threshold values. P3 and P4 simply execute thecode search step for all source ﬁles to analyze the eﬀect of
the ﬁle selection step. P5 is to analyze the eﬀect of the code
search. It combines the ﬁle selection step with the existingnormalized compression distance in our previous work [11].
In the all conﬁgurations, we sorted reported code clones
in ascending order of LZJD so that we can evaluate thecorrectness of LZJD as a source code similarity metric. We
measured the execution time on Windows 10 running on
Xeon E5-2690v3 processor, 64 GB DRAM, and a SSD. We
use a single thread of control.
4.3 Baselines
We compare the proposed method with existing code clone
detection methods as follows.
B1: NCD with Deﬂate (𝑡ℎ = 0.5) is the best conﬁguration in our previous work [11]. The tool compares twocode fragments using Normalized Compression Distance as
described in Section 2.2. We sort reported code clones inascending order of NCD.
B2: Normalized Levenshtein Distance (𝑡ℎ = 0.5) isanother baseline that simply compares code fragments witha query. The normalized Levenshtein distance between codefragments (Levenshtein similarity [29]) is deﬁned as follows.
𝑁 𝐿𝐷 (𝑞, 𝑠) =Precision
Med.
Total

𝐿𝐷 (𝑞, 𝑠)𝑚𝑎𝑥{|𝑞|, |𝑠|}where 𝐿𝐷 (𝑞, 𝑠) is the Levenshtein distance of two sequences𝑞 and 𝑠. It counts the number of edit operations including
insertion, deletion, and modiﬁcation of tokens between aquery code 𝑞 and a code fragment 𝑠. We remove redundantcode clones using the same ﬁltering step as the proposed
method. The code clones are sorted in ascending order of
NLD.
B3-B4: CCFinderX is one of the most popular code

clone detection tools in Japan; it detects two sequences oftokens as a clone pair if they have the same sequence except
for identiﬁer names and constants. We executed the tool todetect code clones between the source code of a product anda ﬁle including a query code fragment, and then ﬁltered out
clone pairs that include no lines of a query code fragment.
We consider a reported clone pair is correct if the pair includes at least a single line of a query code fragment anda single line of faulty code in the ground truth. B3 is thedefault conﬁguration of CCFinderX. It detects code clones
having at least 50 tokens by default. B4 is another conﬁguration that extracts code clones whose length is the sameas a query. Since CCFinderX does not complete a search
for a low threshold, we implemented a specialized tool that
directly compares code fragments obtained from the preprocessor of CCFinderX and reports only code clones whose
size is |𝑞|. These conﬁgurations result in lists of code clones
without a ranking mechanism.
B5-8: NiCad is a tool that has achieved both high precision and recall for various types of code clones [30]. The
tool compares a pair of code blocks or functions, and reports
them as a clone pair if they are similar. We ﬁlter out clone
pairs that include no lines of a query code fragment. We
consider a reported clone pair is correct if the pair includes
both a query code fragment and a faulty code fragment in
the ground truth. We try four conﬁgurations comprising twolevels of code clones (block-level and function-level) andtwo thresholds (3 lines and 10 lines of code). While NiCad
reports a list of code clones with their similarity values, we
do not use the similarity values for sorting code clones because they do not represent the similarity of faulty sourcecode fragments.
B9: CBCD (Estimated) is the baseline we have created using the CBCD method [5], [14]. Since the original
implementation of CBCD is publicly unavailable, we havereceived the source code of the tool from the authors. Nevertheless, we could not execute the tool due to technicalproblems. Instead of the tool execution, we analyzed theimplementation details described in the technical report [14]

ISHIO et al.: NCDSEARCH: SLIDING WINDOW-BASED CODE CLONE SEARCH USING LEMPEL-ZIV JACCARD DISTANCE

7

500
200

+

100
Rank

50
20
10
5

for (var i=0; i < row.Cells.Count; i++){if (row.Cells[i].Value == null){
break;
continue;}
ret.Add((string)row.Cells[i].Value);
}

2
1
LZJD

Fig. 3

NCD−Deflate

NLD

Fig. 4 An actual bug ﬁx in the company (written in C#). The identiﬁers
are anonymized. The bug ﬁx replaced a break statement indicated by “-”with a continue statement indicated by “+”. The same bug was found ina code clone of this code fragment.

Distributions of ranks of faulty code fragments

and then estimated only the precision and recall. This was
possible because the technical report classiﬁed queries into
three groups:“N1: no false positives, no false negatives,”“N2: no false positives, some false negatives,” and “N3:some false positives, no false negatives.” The report also
describes that false positives are function calls when a query
includes only a function call without data/control dependencies (i.e. statements) among them. For example, in caseof Fig.1, CBCD reports all perm_fmgr_info function callsites in the program. Using the information, we counted
the number of source code lines calling the functions in theN3 queries as false positives. The number of false negatives (six) is also obtained from the technical report. Using
the numbers of false positives and negatives, we estimatedthe precision and recall of CBCD. The execution time isunavailable because we did not execute the tool.
4.4 Result
Table 2 shows the performance metrics of the tools: the number of reported clones, the number of detected faulty code
clones, precision, recall, mean average precision (MAP),
and the execution time. As the metrics vary by query, the“Med.” columns show the medians of those values. The“Total” columns show total values for all queries.
The accuracy of the proposed method (P1 and P2) iscomparable to the B1 conﬁguration. P1 reported a smaller
number of false positives but missed several clones than B1.
P2 resulted in no false negatives but more false positives
than B1. Compared with B2, the proposed method is more
precise. The MAP column shows that cloned faulty codefragments are similarly ranked in P1, P2, B1 and B2. Fig.3
shows the distributions of ranks of faulty code fragmentsin three distances LZJD (P1 and P2), NCD (B1), and NLD(B2). The result shows that LZJD successfully worked as an
approximation of NCD.
While keeping the accuracy, the proposed method is
20x faster than B1 according to the total time. In case of
the conﬁguration P1, the most time-consuming query took
at most 83 seconds for detecting clones in Linux kernel.
According to P3–P5, both of the ﬁle selection and code

search steps eﬀectively reduced the search time.
The default conﬁguration of CCFinderX (B3) detectedcloned faulty code fragments, if they are included in large
code clones. While the result is precise, some faulty codefragments are missing because they have additional tokens(i.e. type-3 clones) that could not be handled by CCFinderX. Some other fragments are also missing because the preprocessor accidentally ﬁltered out certain queries and theirclones as “uninteresting” code fragments. A lower threshold(B4) does not improve a result. B4 missed some code clones
detected by B3 because large code clones may accidentally
include queries and their peers even if they are not directly
corresponding to each other.
NiCad (B5–B8) reported a small number of code clones.
This is because code clones in the dataset are neither blocklevel nor function-level.
The accuracy of the proposed method is also comparable to CBCD (B9). Although we did not use control and data
dependence analysis, our textual similarity detected semantically similar code clones. This is probably because faulty
code clones included similar identiﬁers to the query codefragments.
5.

User Evaluation

We have deployed the tool for NEC Corporation. The software engineering group in the company has already used theB1 conﬁguration of the tool in the group and several ongoing projects. The group implemented a GUI tool to executea search, show the search result in a table, and highlight a
selected code clone on a source code editor.
The software engineering group decided to use the P1
conﬁguration as default. To decide the default conﬁguration,
they tested P1 and P2 conﬁgurations against two cases offaulty code clones found in the company (Fig.4 is one of thecases). As a result, they preferred P1 to P2 because P1 ismore precise. They think that the code clone detection stepis perceived as extra work for regular developers; they would
like to encourage developers to quickly inspect code clones
in their daily tasks.
The new tool is distributed on an internal website forsoftware developers of the company. The tool is downloaded
by 101 developers in the company after the ﬁrst company-

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

8
0

5

10

15

False positives
Detection time
Supported languages
User interface
Strong agree

Agree

NeutralDisagreeStrong Disagree

Fig. 5 Responses to the Questionnaire. We asked four questions: “Do
you need the improvement on ...”

wide announcement. After a few months, we sent out questionnaires to those users. We have analyzed 15 responses
from users. The questionnaires included the following questions:
1. What is your purpose of usage?
2. Do you need the improvement on the following aspects?
• False positives• Detection time
• Supported languages• User interface
3. Do you continue to use the tool?
The second question collected answers using a ﬁve-level
Likert scale. “Strong Agree” and “Agree” answers indicatethat the aspect is unsatisfactory for the users.
We found three purposes of usage: code clone searchin multiple products, bug-ﬁxing in a single product, andtechnical interest. 40% of the users answered that they would
like to search the same bugs in related software products.
33% of the respondents answered that they would like tosearch source code when they have to review and ﬁx multiple
source code locations. The other users are simply interested
in the new software development tool.
Fig.5 shows the answers to the second question on thenecessity of further improvements. Regarding the number offalse positives, 40% of users selected either “Strong Agree”
or “Agree”; in other words, they requested further improvements. A possible future direction for reducing false positives is taking semantic aspects of source code into accountbecause our method utilizes only a textual similarity.
Regarding the detection time, it is satisfactory for 33%
of users who selected “Strong Disagree”, while 33% of users
requested further improvements. This result shows that thetime eﬃciency is really important for industrial users. Our
method is recognized as practical to a certain degree.
Supporting additional languages is also requested by
33% of users. This is probably because the tool did notsupport programming languages used in their projects; webelieve that our implementation can support those languages
by including lexers of the languages.
Regarding the user interface, only 20% of users selected“Disagree”. No users selected “Strong Disagree.” The resultshows that a simple user interface that takes as a query andreports a list of source code location is satisfactory for mostof users.
For the last question, 73% (95% CI [52.2, 92.8]) of
the respondents answered that they will continue to use thetool for their software development tasks. The result showsthat the overall performance of the tool is acceptable forthe users. One respondent stated: “I often execute Visual
Studio’s search function several times for a bug-ﬁxing task.
I think I can search such code fragments at once.”
The respondents also gave us comments for future improvements. One respondent requested a semantic search:“I would like to search a particular type of code fragmentsthat are syntactically similar but semantically diﬀerent. For
example, I had to search final non-static ﬁelds in an
actual bug-ﬁxing task. Supporting such a search would be
beneﬁcial.” Another respondent requested to support natural
language text included in comments and document ﬁles.
6. Conclusion
In this study, we proposed a code clone detection method thateﬃciently uses Lempel-Ziv Jaccard Distance. While the proposed method keeps accuracy, the method is 20x faster thanthe previous method based on Normalized Compression Distance. The tool has been deployed in the NEC Corporation;
the user evaluation shows that the performance is acceptablefor industrial developers.
In future work, we would like to take semantic aspectsof source code into account to improve eﬀectiveness, while
keeping the eﬃciency. Another direction is monitoring thelong-term eﬀect in projects so that we can identify best practices to use the tool.
References[1] A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler, “An empirical
study of operating systems errors,” Proceedings of the 18th ACM
Symposium on Operating Systems Principles, pp.73–88, 2001.
[2] N.H. Pham, T.T. Nguyen, H.A. Nguyen, and T.N. Nguyen, “Detection of recurring software vulnerabilities,” Proceedings of theIEEE/ACM International Conference on Automated Software Engineering, pp.447–456, 2010.
[3] R. Yue, N. Meng, and Q. Wang, “A characterization study of repeatedbug ﬁxes,” Proceedings of the 2017 IEEE International Conference
on Software Maintenance and Evolution, pp.422–432, 2017.
[4] Y. Dang, D. Zhang, S. Ge, R. Huang, C. Chu, and T. Xie, “Transferring code-clone detection and analysis to practice,” 2017 IEEE/ACM
39th International Conference on Software Engineering: Software
Engineering in Practice Track, pp.53–62, 2017.
[5] J. Li and M.D. Ernst, “CBCD: Cloned buggy code detector,” Proceedings of the 34th IEEE/ACM International Conference on Software
Engineering, pp.310–320, 2012.
[6] S. Horwitz, T. Reps, and D. Binkley, “Interprocedural slicing using
dependence graphs,” ACM Transactions on Programming Languages
and Systems, vol.12, no.1, pp.26–60, 1990.
[7] M. Li, X. Chen, X. Li, B. Ma, and P. Vitanyi, “The similarity metric,”
IEEE Transactions on Information Theory, vol.50, no.12, pp.3250–
3264, 2004.
[8] X. Chen, B. Francia, M. Li, B. McKinnon, and A. Seker, “Shared
information and program plagiarism detection,” IEEE Transactions
on Information Theory, vol.50, no.7, pp.1545–1551, 2004.
[9] L. Zhang, Y. ting Zhuang, and Z. ming Yuan, “A program plagia-

ISHIO et al.: NCDSEARCH: SLIDING WINDOW-BASED CODE CLONE SEARCH USING LEMPEL-ZIV JACCARD DISTANCE

9rism detection model based on information distance and clustering,”
Proceedings of the 2007 International Conference on Intelligent Pervasive Computing, pp.431–436, 2007.
[10] C. Ragkhitwetsagul, J. Krinke, and D. Clark, “Similarity of sourcecode in the presence of pervasive modiﬁcations,” Proceedings of the
16th International Working Conference on Source Code Analysis
and Manipulation, pp.117–126, 2016.
[11] T. Ishio, N. Maeda, K. Shibuya, and K. Inoue, “Cloned Buggy Code
Detection in Practice Using Normalized Compression Distance,”
Proceedings of the 2018 IEEE 34th International Conference on
Software Maintenance and Evolution, pp.591–594, 2018.
[12] E. Raﬀ and C. Nicholas, “An alternative to ncd for large sequences,lempel-ziv jaccard distance,” Proceedings of the 23rd ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining,
pp.1007–1015, 2017.
[13] E. Raﬀ and C. Nicholas, “Lempel-Ziv Jaccard Distance, an eﬀective alternative to ssdeep and sdhash,” Digital Investigation, vol.24,
pp.34–49, 2018.
[14] J. Li and M.D. Ernst, “CBCD: Cloned buggy code detector,” techreport UW-CSE-11-05-02, University of Washington, 2012.
[15] M. Fowler, Refactoring - Improving the Design of Existing Code,
Addison Wesley object technology series, Addison-Wesley, 1999.
[16] C.K. Roy, J.R. Cordy, and R. Koschke, “Comparison and evaluationof code clone detection techniques and tools: a qualitative approach,”
Science of Computer Programming, vol.74, no.7, pp.470–495, 2009.
[17] T. Kamiya, S. Kusumoto, and K. Inoue, “CCFinder: a multilinguistic
token-based code clone detection system for large scale source code,”IEEE Transactions on Software Engineering, vol.28, no.7, pp.654–
670, 2002.
[18] C.K. Roy and J.R. Cordy, “An Empirical Study of Function Clones
in Open Source Software,” Proceedings of the 2008 15th Working
Conference on Reverse Engineering, pp.81–90, 2008.
[19] Lucia, F. Thung, D. Lo, and L. Jiang, “Are faults localizable?,”Proceedings of the 9th Working Conference on Mining Software
Repositories, pp.74–77, 2012.
[20] J. Jang, A. Agrawal, and D. Brumley, “ReDeBug: Finding unpatched
code clones in entire OS distributions,” Proceedings of the 2012 IEEE
Symposium on Security and Privacy, pp.48–62, 2012.
[21] S. Kim, S. Woo, H. Lee, and H. Oh, “VUDDY: A Scalable Approach
for Vulnerable Code Clone Discovery,” Proceedings of the 2017
IEEE Symposium on Security and Privacy, pp.595–614, 2017.
[22] H. Li, H. Kwon, J. Kwon, and H. Lee, “CLORIFI: software vulnerability discovery using code clone veriﬁcation,” Concurrency andComputation: Practice and Experience, vol.28, no.6, pp.1900–1917,
2015.
[23] V. Balachandran, “Query by example in large-scale code repositories,” Proceedings of the IEEE International Conference on Software
Maintenance and Evolution, pp.467–476, 2015.
[24] C. Ragkhitwetsagul and J. Krinke, “Siamese: Scalable and incremental code clone search via multiple code representations,” Empirical
Software Engineering, vol.24, no.4, p.2236–2284, 2019.
[25] K. Inoue, Y. Miyamoto, D.M. German, and T. Ishio, “Finding CodeClone Snippets in Large Source-Code Collection by ccgrep,” in Open
Source Systems (Proc. IFIP International Conference on Open Source
Systems), pp.28–41, 2021.
[26] J. Ziv and A. Lempel, “Compression of individual sequences via
variable-rate coding,” IEEE Transactions on Information Theory,vol.24, no.5, pp.530–536, 1978.
[27] J. Ziv and A. Lempel, “A universal algorithm for sequential datacompression,” IEEE Transactions on Information Theory, vol.23,
no.3, pp.337–343, 1977.
[28] C. Buckley and E.M. Voorhees, “Evaluating evaluation measure stability,” Proceedings of the 23rd Annual International ACM SIGIR
Conference on Research and Development in Information Retrieval,
pp.33–40, 2000.
[29] M.M. Deza and E. Deza, Encyclopedia of Distances, 4 ed., Springer
Berlin Heidelberg, 2016.

[30] F. Farmahinifarahani, V. Saini, D. Yang, H. Sajnani, and C.V. Lopes,“On precision of code clone detection tools,” Proceedings of the 2019
IEEE 26th International Conference on Software Analysis, Evolution
and Reengineering, pp.84–94, 2019.

Takashi Ishio
received the Ph.D degree in
information science and technology from Osaka
University in 2006. He was a JSPS Research Fellow from 2006-2007. He was an assistant professor at Osaka University from 2007-2017. He
is now an associate professor of Nara Institute of
Science and Technology. His research interests
include program analysis, program comprehension, and software reuse.

Naoto Maeda
received his master’s degree
in informatics from Waseda University in 1999.
He is an AI engineering manager at NEC Corporation, leading R&D of medical imaging AI
technologies.

Kensuke Shibuya
received his master’s degree in informatics from Waseda University in2008. After graduation he joined NEC Corporation. He is currently working on improving
software development by adopting software engineering technologies.

Kenho Iwamoto
received his master’s degree in mechanical engineering from Chiba University in 2013. After graduation he joined NEC
Corporation. He is currently working on improving software development by adopting software
engineering technologies.

IEICE TRANS. INF. & SYST., VOL.Exx–??, NO.xx XXXX 200x

10Katsuro Inoue
received his Ph.D. from Osaka University in 1984. He was an associate
professor of the University of Hawaii at Manoa
from 1984 to 1986. After becoming an assistantprofessor of Osaka University in 1986, he has
been a professor since 1995. His research interests include software engineering, especially
software maintenance, software reuse, empiricalapproach, program analysis, code clone detection, and software license/copyright analysis.