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