|
cannam@89
|
1 A Fast Method for Identifying Plain Text Files
|
|
cannam@89
|
2 ==============================================
|
|
cannam@89
|
3
|
|
cannam@89
|
4
|
|
cannam@89
|
5 Introduction
|
|
cannam@89
|
6 ------------
|
|
cannam@89
|
7
|
|
cannam@89
|
8 Given a file coming from an unknown source, it is sometimes desirable
|
|
cannam@89
|
9 to find out whether the format of that file is plain text. Although
|
|
cannam@89
|
10 this may appear like a simple task, a fully accurate detection of the
|
|
cannam@89
|
11 file type requires heavy-duty semantic analysis on the file contents.
|
|
cannam@89
|
12 It is, however, possible to obtain satisfactory results by employing
|
|
cannam@89
|
13 various heuristics.
|
|
cannam@89
|
14
|
|
cannam@89
|
15 Previous versions of PKZip and other zip-compatible compression tools
|
|
cannam@89
|
16 were using a crude detection scheme: if more than 80% (4/5) of the bytes
|
|
cannam@89
|
17 found in a certain buffer are within the range [7..127], the file is
|
|
cannam@89
|
18 labeled as plain text, otherwise it is labeled as binary. A prominent
|
|
cannam@89
|
19 limitation of this scheme is the restriction to Latin-based alphabets.
|
|
cannam@89
|
20 Other alphabets, like Greek, Cyrillic or Asian, make extensive use of
|
|
cannam@89
|
21 the bytes within the range [128..255], and texts using these alphabets
|
|
cannam@89
|
22 are most often misidentified by this scheme; in other words, the rate
|
|
cannam@89
|
23 of false negatives is sometimes too high, which means that the recall
|
|
cannam@89
|
24 is low. Another weakness of this scheme is a reduced precision, due to
|
|
cannam@89
|
25 the false positives that may occur when binary files containing large
|
|
cannam@89
|
26 amounts of textual characters are misidentified as plain text.
|
|
cannam@89
|
27
|
|
cannam@89
|
28 In this article we propose a new, simple detection scheme that features
|
|
cannam@89
|
29 a much increased precision and a near-100% recall. This scheme is
|
|
cannam@89
|
30 designed to work on ASCII, Unicode and other ASCII-derived alphabets,
|
|
cannam@89
|
31 and it handles single-byte encodings (ISO-8859, MacRoman, KOI8, etc.)
|
|
cannam@89
|
32 and variable-sized encodings (ISO-2022, UTF-8, etc.). Wider encodings
|
|
cannam@89
|
33 (UCS-2/UTF-16 and UCS-4/UTF-32) are not handled, however.
|
|
cannam@89
|
34
|
|
cannam@89
|
35
|
|
cannam@89
|
36 The Algorithm
|
|
cannam@89
|
37 -------------
|
|
cannam@89
|
38
|
|
cannam@89
|
39 The algorithm works by dividing the set of bytecodes [0..255] into three
|
|
cannam@89
|
40 categories:
|
|
cannam@89
|
41 - The white list of textual bytecodes:
|
|
cannam@89
|
42 9 (TAB), 10 (LF), 13 (CR), 32 (SPACE) to 255.
|
|
cannam@89
|
43 - The gray list of tolerated bytecodes:
|
|
cannam@89
|
44 7 (BEL), 8 (BS), 11 (VT), 12 (FF), 26 (SUB), 27 (ESC).
|
|
cannam@89
|
45 - The black list of undesired, non-textual bytecodes:
|
|
cannam@89
|
46 0 (NUL) to 6, 14 to 31.
|
|
cannam@89
|
47
|
|
cannam@89
|
48 If a file contains at least one byte that belongs to the white list and
|
|
cannam@89
|
49 no byte that belongs to the black list, then the file is categorized as
|
|
cannam@89
|
50 plain text; otherwise, it is categorized as binary. (The boundary case,
|
|
cannam@89
|
51 when the file is empty, automatically falls into the latter category.)
|
|
cannam@89
|
52
|
|
cannam@89
|
53
|
|
cannam@89
|
54 Rationale
|
|
cannam@89
|
55 ---------
|
|
cannam@89
|
56
|
|
cannam@89
|
57 The idea behind this algorithm relies on two observations.
|
|
cannam@89
|
58
|
|
cannam@89
|
59 The first observation is that, although the full range of 7-bit codes
|
|
cannam@89
|
60 [0..127] is properly specified by the ASCII standard, most control
|
|
cannam@89
|
61 characters in the range [0..31] are not used in practice. The only
|
|
cannam@89
|
62 widely-used, almost universally-portable control codes are 9 (TAB),
|
|
cannam@89
|
63 10 (LF) and 13 (CR). There are a few more control codes that are
|
|
cannam@89
|
64 recognized on a reduced range of platforms and text viewers/editors:
|
|
cannam@89
|
65 7 (BEL), 8 (BS), 11 (VT), 12 (FF), 26 (SUB) and 27 (ESC); but these
|
|
cannam@89
|
66 codes are rarely (if ever) used alone, without being accompanied by
|
|
cannam@89
|
67 some printable text. Even the newer, portable text formats such as
|
|
cannam@89
|
68 XML avoid using control characters outside the list mentioned here.
|
|
cannam@89
|
69
|
|
cannam@89
|
70 The second observation is that most of the binary files tend to contain
|
|
cannam@89
|
71 control characters, especially 0 (NUL). Even though the older text
|
|
cannam@89
|
72 detection schemes observe the presence of non-ASCII codes from the range
|
|
cannam@89
|
73 [128..255], the precision rarely has to suffer if this upper range is
|
|
cannam@89
|
74 labeled as textual, because the files that are genuinely binary tend to
|
|
cannam@89
|
75 contain both control characters and codes from the upper range. On the
|
|
cannam@89
|
76 other hand, the upper range needs to be labeled as textual, because it
|
|
cannam@89
|
77 is used by virtually all ASCII extensions. In particular, this range is
|
|
cannam@89
|
78 used for encoding non-Latin scripts.
|
|
cannam@89
|
79
|
|
cannam@89
|
80 Since there is no counting involved, other than simply observing the
|
|
cannam@89
|
81 presence or the absence of some byte values, the algorithm produces
|
|
cannam@89
|
82 consistent results, regardless what alphabet encoding is being used.
|
|
cannam@89
|
83 (If counting were involved, it could be possible to obtain different
|
|
cannam@89
|
84 results on a text encoded, say, using ISO-8859-16 versus UTF-8.)
|
|
cannam@89
|
85
|
|
cannam@89
|
86 There is an extra category of plain text files that are "polluted" with
|
|
cannam@89
|
87 one or more black-listed codes, either by mistake or by peculiar design
|
|
cannam@89
|
88 considerations. In such cases, a scheme that tolerates a small fraction
|
|
cannam@89
|
89 of black-listed codes would provide an increased recall (i.e. more true
|
|
cannam@89
|
90 positives). This, however, incurs a reduced precision overall, since
|
|
cannam@89
|
91 false positives are more likely to appear in binary files that contain
|
|
cannam@89
|
92 large chunks of textual data. Furthermore, "polluted" plain text should
|
|
cannam@89
|
93 be regarded as binary by general-purpose text detection schemes, because
|
|
cannam@89
|
94 general-purpose text processing algorithms might not be applicable.
|
|
cannam@89
|
95 Under this premise, it is safe to say that our detection method provides
|
|
cannam@89
|
96 a near-100% recall.
|
|
cannam@89
|
97
|
|
cannam@89
|
98 Experiments have been run on many files coming from various platforms
|
|
cannam@89
|
99 and applications. We tried plain text files, system logs, source code,
|
|
cannam@89
|
100 formatted office documents, compiled object code, etc. The results
|
|
cannam@89
|
101 confirm the optimistic assumptions about the capabilities of this
|
|
cannam@89
|
102 algorithm.
|
|
cannam@89
|
103
|
|
cannam@89
|
104
|
|
cannam@89
|
105 --
|
|
cannam@89
|
106 Cosmin Truta
|
|
cannam@89
|
107 Last updated: 2006-May-28
|
