Abstract
Natural language is remarkably robust against noise; the core meaning of a sentence often survives even when many words are removed. We hypothesize that source code exhibits a similar property, containing essential "wheat" (unique information) and redundant "chaff" (boilerplate or common syntax). By analyzing a corpus of 100 million lines of Java code, we quantify this phenomenon using the Minimal Distinguishing Subset (Minset). Our findings reveal that most methods can be uniquely identified by a tiny fraction of their lexical content—averaging just 1.56 words—providing quantitative evidence for the feasibility of keyword-based programming and advanced code summarization.
Introduction: The Wheat and the Chaff
In natural language, some words are indispensable (like "not" in "I do not like rain"), while others provide structural support but less unique information. Modern software engineering implicitly relies on this concept through tools like code search and completion. However, the extent to which a small subset of words can uniquely represent a complex executable block of code has remained largely unquantified. This study investigates lexical distinguishability: the minimum amount of information required to differentiate one function from millions of others in a massive corpus.
Methodology: Finding the Minset
We treat Java methods as the fundamental unit of code, analogous to sentences. To isolate the "wheat," we define the MINSET (Minimal Distinguishing Subset) as the smallest set of words within a method that does not appear in any other method in the entire corpus.
Finding the absolute smallest subset is an NP-hard problem. To address this, we developed a greedy approximation algorithm. This algorithm iteratively selects the most "distinguishing" words—those appearing in the fewest other methods—until the target method is uniquely identified.
We evaluated this across several lexicons:
- LEX: Raw text, including all variable names and literals.
- LTT: Abstract token types (e.g.,
IDENTIFIER,INTLIT). - MIN1–MIN4: Custom abstractions that progressively filter noise (like local variable names) while retaining structural elements (method names, operators, control keywords).
Dataset and Scale
The study utilized a diverse corpus of approximately 1,000 popular open-source projects (GitHub, Apache, Eclipse, SourceForge), totaling 100 million lines of code and roughly 9 million Java methods. To ensure meaningful results, we focused on methods with at least 50 tokens, filtering out trivial "scaffolding" code like simple getters and setters. A random sample of 10,000 methods was used for intensive MINSET computations.
Key Results: The Sparsity of Information
Our analysis confirms that source code is incredibly sparse in terms of unique information. Most of a program consists of "chaff"—syntactic requirements and common patterns.
- Average MINSET Size: In the raw LEX lexicon, the average MINSET size is only 1.56 words.
- Extreme Compression: No method in our sample required more than 6 words to be uniquely identified. On average, MINSETs comprise only 4% of the total words in a method.
- Yield and Abstraction: In our most refined model (MIN4), over 60% of methods in the 100M LOC corpus could be uniquely identified by a small, meaningful set of keywords.
Discussion and Implications
One surprising finding is that the size of the "wheat" does not scale linearly with code complexity; even large methods often have tiny MINSETs. Furthermore, while raw text (LEX) is the most distinguishable, it can be noisy due to typos or unique variable names. More abstract lexicons (like MIN4) produce MINSETs that resemble human-readable summaries, suggesting that these mathematical "wheat" subsets align with semantic essence.
Conclusion
This research provides the first large-scale quantitative evidence that source code is highly redundant. The fact that a typical method can be uniquely indexed by fewer than two words has significant implications for the development of alternative programming models, more efficient code search engines, and automated documentation tools. Future work will explore whether these findings extend to other programming paradigms and how to bridge the gap between lexical distinguishability and functional behavior.
Summary updated