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