Automatic Categorization Tool for Open Software
Repositories
Shinji Kawaguchi†

Pankaj K. Garg††

Makoto Matsushita††Graduate School of Information Science and††Zee Source
1684 Nightingale Avenue, Suite 201
Sunnyvale, California, 94807, USA

Technology, Osaka University
1-3 Machikaneyama, Toyonaka, Osaka
560-8531, Japan

garg@zeesource.net{s-kawagt, matusita,
inoue}@ist.osaka-u.ac.jp

ABSTRACT

Katsuro Inoue†ways:

The world of Open Source software has demonstrated the remarkable appeal of communal software development. Large number ofsoftware projects can leverage, reuse, and coordinate their workthrough Internet and web-based technology. For example, SourceForge currently hosts about sixty thousand software systems. Similar strategies have been suggested for corporate software development, through notions like Corporate Source and Progressive Open
Source [6, 7]• Several similar software can be grouped together in a category for ease of browsing. For example, SourceForge [17]categorizes software according to their function (editors, databases,etc.), and also has the notion of software foundries for related
software.

When used in a corporate setting, infrastructures for project information sharing present new opportunities. For example, one would
like to know all projects that have something in common, so thatthe project groups can collaborate and share their work. With thousands of projects, manually locating related projects can be difficult. Hence, we propose to use automatic software categorization
to find clusters of related software projects, using only the sourcecode from projects. Our experiments with a small set of C programs demonstrates potential for automatic categorization of software systems without human aid.

1. Developers can learn “best practices” and programming
idioms from existing software systems. From related
software systems, they can get strategies or hints forsoftware evolution. They can even evolve their software systems based on related software systems, andnot have to create it from scratch.

1.

INTRODUCTION

The rapid use of Internet and Web-based technology has given rise
to a novel, global software archiving service, pioneered in the Open
Source community through SourceForge [17]. More recently, several large corporations are realizing the benefits of such services
for their own, proprietary software development. For example,
Hewlett-Packard Company, IBM, Motorola, Nokia, and Xerox, aresome of the corporations that are known to have deployed sucharchival service for their own internal corporate network.
For large software archives, categorizing their contents for browsing and searching is essential for effective utilization of the software archive. Automatic categorization would be helpful in several• Developers working on a software system may be informed
about related software. Finding related software systems has
following advantages.

2. Developers can leverage each other’s work and promote
more reuse. This becomes specially useful in situations
like Corporate Source [7], where global groups in companies may not be aware of the relationship among theirwork [9].
In the past, such relationships have been determined by hand. Manual categorization generally requires deep understanding of not only
the target software system, but also other software systems and theirclassification policy. With the increase in the number of softwaresystems, e.g., SourceForge now has over sixty thousand softwaresystems registered and continues to evolve, such manual identification is not enough.
Automatic categorization of software systems is a novel and intriguing challenge on software archive evolution. Past work in software engineering (e.g., see [4, 16]), has focused on determining
intra-component relations of one given software system. We, however, propose finding inter-component relations of many softwaresystems.
In this paper, we propose software automatic categorization system
based on Latent Semantic Analysis(LSA). LSA is a method for extracting and representing the contextual-usage meaning of words bystatistical computations applied to a large corpus of text [11]. LSA

has found a variety of uses ranging from understanding human cognition [11] to data mining [5]. Also, it is used for clustering components in a software system [14] and recovering document-to-source
links [15].
We apply LSA for determining categories of software systems. We
implemented the proposed method, and report on experimental results.

2.

RELATED WORKS

Maarek et al. applied free-text indexing approach for software classification [13, 8]. They retrieved information from Unix man pages
and classified Unix tools.
While quality and granularity of Unix man pages are highly uniform, the amount and quality of documents differ with softwaresystems. Some software may have complete documentation, whileothers may have no or few documentation for their implementations.

Latent Semantic Analysis, LSA, is a practical method for the characterization of word meaning. LSA produces measures of wordword, and passage-passage relations which are well correlated withsemantic similarity [11]. The method creates a vector descriptionof documents. This representation is used for comparing and indexing documents, and various similarity measures can be defined.
Consider the six simple documents in Figure 1. In LSA, these documents are represented by a matrix shown in Table 1. Each column
means a document and each row represents a word which may appear in the documents. Cell entries show the occurrence of the wordin the document.
c1: Human machine interface for ABC computer applications
c2: A survey of user opinion of computer system response timec3: Relation of user perceived response time to error measurement
m1: The generation of random, binary, ordered trees
m2: Graph minors IV: Widths of trees and well-quasi-ordering
m3: Graph minors: A survey

From the viewpoint of retrieving information from source code,some existing clustering methods cluster one software into somefunctional parts for program understanding. Such software clustering methods use Latent Semantic Analysis [14], Self-Organizing
Map [2], file structure and file names [1] or structure of program
like call graph [3, 12].
In our previous work [10], we have tried measurement methods ofsoftware similarities. The hope was that we will relate “similar”
systems together, and determine orthogonal categories like “editors,” “databases,” and so forth. We applied LSA to software systems and found that software similarity values are reflected only
by most influential aspects of software systems. For example, thesimilarity value between database software with GTK interface andeditors using GTK is very high. Although this phenomenon is notwhat we had hoped for, as be report in the rest of the paper, it is notnecessarily bad.

3.

Figure 1: Example Input Documents
computeruser
responsetime
surveytrees
graphminors

c1
1
0
0
0
0
0
0
0

c2
1
1
1
1
1
0
0
0

c3
0
1
1
1
0
0
0
0

m1
0
0
0
0
0
1
0
0

m2
0
0
0
0
0
1
1
1

m3
0
0
0
0
1
0
1
1

Table 1: An Example of LSA Matrix
Each row vector of this matrix indicates the characteristics of theword through the whole documents occurrences. This row vector
can be used to determine the similarity of two words. A simple
similarity definition used here is cosine of two vectors.

CATEGORIZATION METHOD

The result of our previous work cited above indicates that softwaresystems have multiple ’functional aspects’. Functional aspects are,for example, “compiler”, “editor”, “database”, “runs on Windows”,“supporting regular expression,” and so forth. Consider an editor
on Windows. This editor has not only “editor” functional aspect,
but also “runs on Windows” functional aspect.
The software systems can be categorized with functional aspects on
a nonexclusive basis. If a categorization is mutually exclusive, thecategorization may capture only a few functional aspects.
We focus on identifiers (variable name, function name and so on)
included in source code to retrieve a functional aspect. For example, “gtk_window” identifier represents some window, andsource codes near the identifier would contain GUI operation.

In LSA, single value decomposition (SVD) is applied to the matrix.
SVD is a form of factor analysis and acts as a method for reducing the dimensionality of the matrices. Why does LSA apply suchtranslation? This is because a simple term-by-document matrix
does not capture relationship among terms. Two documents showhigh similarity only when the documents have some same words;
however, there are many synonyms. Thus similar documents do
not always share completely same words. They may contain many
synonyms. Using SVD, LSA can retrieve such undirectional relationship among documents. For more details, please refer [11].

3.2

Overview of Classification Method

Our method consists on 7 parts, explained in brief below:
1. Extract identifiers.

As stated above, identifiers may represent a part of functions implemented in the program. If relationship between identifiers arefound, they would represent one functional aspect. To determine
relationships between identifiers, we use Latent Semantic Analysis(LSA), an information retrieval method explained below.

3.1

Latent Semantic Analysis (LSA)

First, we extract all identifiers from source code of softwaresystems. We don’t use reserved words in programming language and words in comments. Reserved words are meaningless from the viewpoint of function. Comments are abstract description, but amount and quality of comments ineach software systems vary widely. Thus we cut out reserved
words and comments.

2. Create identifier-by-software matrix.
We create an identifier-by-software matrix, similar to the wordby-document matrix of Table 1.
3. Remove meaningless identifiers.
Before performing LSA, we remove identifiers that appear
in only one software system, or in more than half of software systems. Identifiers appearing in only one software are
not meaningful in LSA. And, identifiers appearing in morethan half of software systems are probably a general termand have no affect on categorization.
4. Perform LSA.
We perform LSA for the identifier-by-software matrix without meaningless identifiers.
5. Compute cosine of each identifiers and perform cluster analysis.
From the matrix of LSA result, we compute cosine values ofeach identifiers. Thereafter, we apply cluster analysis using
calculated similarities. Cluster analysis is statistical analysis
method that cluster individuals into clusters based on similarity among individuals.
6. Make software clusters from identifier clusters.
From each identifier clusters, we retrieve software systems
that contain one or more identifiers in the cluster, and makethem a corresponding software cluster.
7. Make titles of software clusters.
We obtain software clusters by previous steps, however, eachsoftware cluster needs description that explains what software systems are included. As titles, we use the ten highest
score identifiers in the clusters.

4.

EXPERIMENTS

As an implementation of our method, we created a prototype system. We experimented categorization of software systems using
the prototype. The overall goals of our experiment were: Does our
prototype categorize proper by target systems compared with existing manual categorization? Can our prototype categorize by thelibraries use in the system?

4.1

Experiment Process

We collect sample data from SourceForge. We selected 41 C programs in five categories from SourceForge. The list of categories
and software systems are in Table 2. Then we ran our categorization tool on the 41 programs.

4.2

ResultTable 3 shows a part of the categorization result by our method.
Each row represents one cluster.
We got 40 clusters in total. The target systems in 18 clusters fall inthe same categorization as SourceForge categorization. There are
8 clusters in which all software systems depend on same library or
have same architecture. In top 20 clusters, 17 clusters fall in thesame categorization in SourceForge or same library.
For example, cluster 3, 8 or 9 are clustered since the software systems in those clusters use the same library. Cluster 3 contains
software systems using YACC(Yet Another Compiler-Compiler).

Cluster 8 and 9 contains software systems using GTK. In the samemanner, we can get the following clusters.
Cluster 22 Software systems using regular expression pattern matching library.
Cluster 25 Software systems implementing JNI(Java Native Interface).
Cluster 30 Software systems using getopt, a function which parses
a command line argument.
Cluster 32 Software systems implementing Python/C.
Cluster 35 Software systems using YACC(Yet Another CompilerCompiler).
On the other hand, there are 12 software systems that are not classified into any categories.

4.3

Discussion

Comparing with existing categorization, many clusters of our result
follow existing categorization however, our result does not coverwhole existing categorization. This is because our result has software systems that are not classified any categories. Our method categorizes based on appearance frequency of identifiers. This makes
software systems that have few tokens tend to be not classified any
categories.
We verify that our method can retrieve new categorization that are
not considered by existing categorization. Such categorizations are:(1) by libraries (GTK, yacc, etc.), and (2) by depending architecture (JNI, Python/C, etc.). Our method does not need any humanknowledge. Thus, if a new library appears, our method can follow
such change automatically.
About cluster titles, there are some unidentifiable titles like cluster
1; however, cluster 4 and 6 have clear-cut titles “AVI” and “board,ply”. The clusters with software systems using same library tend tohave clear-cut titles.

5.

CONCLUSION

In this paper, we have proposed automatic categorization method
for many software systems. Our method finds categorization clusters and classifies software systems based on the clusters. We haveshown this method can classify without any knowledge about target
software systems.
For future work, we will seek how to determine parameters andretrieving intuitive cluster titles. Furthermore, we will add largescale experimentation. To do this, we need to improve system performance and scalability.

6.

REFERENCES[1] N. Anquetil and T. Lethbridge. Extracting concepts from filenames; a new file clustering criterion. In International
Conference on Software Engineering,(ICSE’98), pages
84–93, Apr 1998.
[2] A. Chan and T. Spracklen. Discoverying common features insoftware code using self-organising maps. In International
Symposium on Computational Intelligence (ISCI’2000),
Kosice, Slovakia, August 2000.

Categoryboardgamecompilers
database
editorvideoconversion
xterm

SoftwareSjeng-10.0, bingo-cards, btechmux-1.4.3, cinag-1.1.4, faile 1 4 4, gbatnav-1.0.4, gchch-1.2.1, icsDrone, libgmonopd-0.3.0, netships-1.3.1, nettoe-1.1.0, nngs-1.1.14, ttt-0.10.0
clisp-2.30, csl-4.3.0, freewrapsrc53, gbdk, gprolog-1.2.3, gsoap2, jcom223, nasm-0.98.35, pfe-0.32.56,
sdcc
centrallix, emdros-1.1.4, firebird-1.0.0.796, gtm V43001A, leap-1.2.6, mysql-3.23.49, postgresql-7.2.1
gedit-1.120.0, gmas-1.1.0, gnotepad+-1.3.3, molasses-1.1.0, peacock-0.4
dv2jpg-1.1, libcu30-1.0, mjpgTools, mpegsplit-1.1.1
R6.3, R6.4
Table 2: The list of sample software systems[3] K. Chen and V. Rajlich. Case study of feature location using
dependency graph. In 8th International Workshop on
Program Comprehension (IWPC’00), pages 231–239,
Limerick, Ireland, June 2000.
[4] S. C. Choi and W. Scacchi. Extracting and restructuring thedesign of large systems. IEEE Software, 7(1):66–71, Jan
1990.
[5] S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W.
Furnas, and R. A. Harshman. Indexing by latent semantic
analysis. Journal of the American Society of Information
Science, 41(6):391–407, 1990.
[6] J. Dinkelacker and P. Garg. Corporate Source: Applying
Open Source concepts to a corporate environment (Position
Paper). In Proceedings of the 1st ICSE workshop on Open
Source software engineering, Toronto, Canada, 2001.
[7] J. Dinkelacker, P. Garg, D. Nelson, and R. Miller. Progressive
Open Source. In Proceedings of the International Conference
on Software Engineering, Orlando, Florida, 2002.
[8] W. B. Frakes and T. Pole. An empirical study ofrepresentation methods for reusable software components.
IEEE Transactions on Software Engineering, 20(8):617–630,
1994.
[9] J. Herbsleb and A. Mockus. An Empirical Study of Speed
and Communication in Globally-Distributed Software
Development. IEEE Transactions. Software Engineering,
2003.
[10] S. Kawaguchi, P. K. Garg, M. Matsushita, and K. Inoue.
Automatic categorization algorithm for evolvable softwarearchive. In 2003 International Workshop on Principles ofSoftware Evolution(IWPSE 2003), Sep 2003.
[11] T. K. Landauer and S. T. Dumais. Latent Semantic Analysis
and the Measurement of Knowledge. In Educational Testing
Service Conference on Natural Language Processing
Techniques and Technology in Assessment and Education,
princeton, 1994.
[12] G. A. D. Lucca, A. R. Fasolino, F. Pace, P. Tramontana, andU. D. Carlini. Comprehending web applications by aclustering based approach. In Proc. of 10th International
Workshop on Program Comprehension(IWPC’02), pages
261–270, Paris, France, June 2002.
[13] Y. S. Maarek, D. M. Berry, and G. E. Kaiser. An information
retrieval approach for automatically constructing software
libraries. IEEE Transactions of Software Engineering,17(8):800–813, 1991.

[14] J. I. Maletic and A. Marcus. Using latent semantic analysis
to identify similarities in source code to support program
understanding. In 12th IEEE International Conference on
Tools with Artificial Intelligence (ICTAI’00), pages 46–53,
November 2000.
[15] A. Marcus and J. I. Maletic. Recovering
documentation-to-source-code traceability links using latentsemantic indexing. In Proceedings of the 25th International
Conference on Software Engineering(ICSE2003), pages
125–135, Portland, OR, May 2003.
[16] R. Schwanke. An intelligent tool for re-engineering softwaremodularity. In Proc. of 13th International Conference on
Software Engineering, pages 83–92, Austin, Texas, USA,May 1991.
[17] SOURCEFORGE.net. http://sourceforge.net.

No.
1
2

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

Title of cluster
AOP, emitcode, IC RESULT, IC LEFT, aop, aopGet, IC RIGHT, pic14 emitcode,
iCode, etype
CASE IGNORE,
CASE GROUND STATE,
screen,CASE PRINT,
CASE BYP STATE,
Widget,TScreen,CASE IGNORE STATE,CASE PLT VEC, CASE PT POINT
YY BREAK, yyvsp, yyval, DATA, yy current buffer, tuple, yy current state,
yy c buf p, yy cp, uint32
AVI, cinfo, OUTLONG, avi t, AVI errno, hdrl data, OUT4CC, nhb, ERR EXIT,
str2ulongdomainname, msgid1, binding, msgid2, domainbinding, pexp, builtin expect,transmem list, codeset, codesetp
board, num moves, ply, pawn file, npiece, pawns, moves, white to move, move s,
promoted
xdrs, blob, DB, UCHAR, XDR, mutex, key length, logp, page no, bdb
domainname, N , binding, gchar, GtkWidget, PARAMS, codeset, gpointer,loaded l10nfile, argz
GtkWidget, gchar, gpointer, gint, widget, gtk widget show, N , g free, dialog,
g return if fail
AOP, emitcode, esp, IC RESULT, IC LEFT, obstack, aop, mov, aopGet,
IC RIGHT
tuple, uint32, plan, int32, lsn, elm, rec, interp, TCL ERROR, finfo
xdrs, blob, DB, UCHAR, XDR, mutex, key length, logp, page no, bdb
UCHAR, relation, stmt, trigger, yyvsp, yyval, t data, plan, dbname, USHORT
fout, interp, TCL ERROR, typ, YY RULE SETUP, List, DATA, Tcl Interp, id,
YY BREAK
GtkWidget, gchar, gpointer, dlg, gint, g free, gtk widget show, gtk, GList,
GTK BOXUCHAR, relation, stmt, trigger, yyvsp, yyval, t data, plan, dbname, USHORT
AOP, emitcode, mfp, ic, uchar, IC RESULT, IC LEFT, aop, aopGet, IC RIGHT
adr, FX, word, stm, ED, xt, REF, prop, term, FP
AOP, emitcode, IC RESULT, IC LEFT, aop, aopGet, IC RIGHT, pic14 emitcode,
iCode, etypedyn, FPRINTF, process id, p offset, ctl, rab, que, io ptr, prior, PRINTF
dyn, FPRINTF, process id, p offset, ctl, rab, que, io ptr, prior, PRINTF
regparse, dbp, mech, reginput, flagp, NOTHING, tuple, db, P, regnoderectype, argp, rec, fileid, save errno, data len, qp, argpp, int4, dbp
AOP, emitcode, IC RESULT, IC LEFT, aop, aopGet, IC RIGHT, pic14 emitcode,
iCode, etypejobject, JNIEnv, JNICALL, JNIEXPORT, jint, jstring, interp, TCL ERROR, objv,
TCL OK
entrypoint, USHORT, TEXT, yyvsp, raddr, R, UCHAR, yyval, blob, REQ
int32 t, dbp, cinfo, net, unpack, argp, sinfo, cur1, purpose, mysql
AOP, emitcode, mfp, ic, uchar, IC RESULT, IC LEFT, aop, aopGet, IC RIGHTUSHORT, UCHAR, blob, REQ, NULL PTR, hIcon, SCHAR, interp, wndclass,bdb
optind, nextchar, P, optstring, last nonopt, option index, uchar, optarg, pfound,dbp
int4, ctl, tn, rec, semid, blkno, ti, oprtype, save errno, AH
notify, mech, PyObject, fargs, Node, Name, pset, zone, tprintf, NOTHING
interp, notify, dbp, tuple, mech, PyObject, uint32, plan, int32, buff
adr, stm, AOP, emitcode, operands, ASSERT, IC RESULT, pred, lg, REF
yyvsp, yyn, PARAMS, codeset, domainname, msgid1, binding, msgid2, yylsp,
domainbinding
ERREXIT, picture, pool id, USHORT, get buffer, output buf, cinfo, xxx,
UCHAR, streams
REF, dyn, USHORT, vec, path name, clause, STATUS, E, UCHAR, CSB
AOP, emitcode, pfile, ic, IC RESULT, IC LEFT, aop, aopGet, IC RIGHT,
pic14 emitcode
ic, ply, npiece, score, AOP, pawn file, uchar, bking loc, wking loc, emitcode
clause, cinfo, pred, ci, Group, Np, word, X, A, tmp4

Softwarecompilers/gbdk, compilers/sdcc

The number of tokens
8597

xterm/R6.3, xterm/R6.4

2160

compilers/gbdk,
database/mysql-3.23.49,
database/postgresql-7.2.1
videoconversion/dv2jpg-1.1, videoconversion/libcu30-1.0,
videoconversion/mjpgTools
boardgame/gbatnav-1.0.4, boardgame/gchch-1.2.1

223

boardgame/Sjeng-10.0,
boardgame/cinag-1.1.4,
boardgame/faile 1 4 4
database/firebird-1.0.0.796, database/mysql-3.23.49
boardgame/gbatnav-1.0.4,
boardgame/gchch-1.2.1,
editor/gnotepad+-1.3.3, editor/peacock-0.4
boardgame/gbatnav-1.0.4, editor/gedit-1.120.0, editor/gmas1.1.0, editor/gnotepad+-1.3.3, editor/peacock-0.4
compilers/clisp-2.30, compilers/gbdk, compilers/sdcc

154

database/mysql-3.23.49, database/postgresql-7.2.1
database/firebird-1.0.0.796, database/mysql-3.23.49
database/firebird-1.0.0.796, database/postgresql-7.2.1
compilers/freewrapsrc53, compilers/gbdk, compilers/gsoap2,
database/postgresql-7.2.1
editor/gedit-1.120.0, editor/gmas-1.1.0, editor/gnotepad+1.3.3
database/firebird-1.0.0.796, database/postgresql-7.2.1
compilers/gbdk, compilers/sdcc, database/mysql-3.23.49
compilers/gprolog-1.2.3, compilers/pfe-0.32.56
compilers/gbdk, compilers/sdcc, database/firebird-1.0.0.796

79
73
68
50

database/firebird-1.0.0.796, database/gtm V43001A src linux
database/firebird-1.0.0.796, database/gtm V43001A src linux
boardgame/btechmux-1.4.3,
database/leap-1.2.6,
database/mysql-3.23.49
database/gtm V43001A src linux, database/mysql-3.23.49
compilers/gbdk, compilers/sdcc, videoconversion/mjpgTools

29
27
26

compilers/freewrapsrc53, compilers/jcom223, compilers/pfe0.32.56, database/mysql-3.23.49
compilers/clisp-2.30, database/firebird-1.0.0.796
database/mysql-3.23.49, videoconversion/mjpgTools
compilers/gbdk, compilers/sdcc, database/mysql-3.23.49
compilers/freewrapsrc53, database/firebird-1.0.0.796

24

boardgame/ttt-0.10.0, compilers/clisp-2.30, database/mysql3.23.49
database/gtm V43001A src linux, database/postgresql-7.2.1
boardgame/btechmux-1.4.3, database/postgresql-7.2.1
boardgame/btechmux-1.4.3,
database/mysql-3.23.49,
database/postgresql-7.2.1
compilers/gprolog-1.2.3, compilers/sdcc
boardgame/gbatnav-1.0.4,
boardgame/gchch-1.2.1,
compilers/clisp-2.30
database/firebird-1.0.0.796, videoconversion/mjpgTools

15

compilers/gprolog-1.2.3, database/firebird-1.0.0.796
compilers/gbdk, compilers/sdcc, database/postgresql-7.2.1

8
7

boardgame/Sjeng-10.0, compilers/gbdk
compilers/gprolog-1.2.3, database/postgresql-7.2.1, videoconversion/mjpgTools

7
6

Table 3: 41

177
165

118
118
104
100

46
43
36
35
31

26
26

17
17
16
16

14
11
10
9
9
9