Find Unique Characters in a File

问题:

I have a file with 450,000+ rows of entries. Each entry is about 7 characters in length. What I want to know is the unique characters of this file.

For instance, if my file were the following;

Entry
-----
Yabba
Dabba
Doo

Then the result would be

Unique characters: {abdoy}

Notice I don't care about case and don't need to order the results. Something tells me this is very easy for the Linux folks to solve.

Update

I'm looking for a very fast solution. I really don't want to have to create code to loop over each entry, loop through each character...and so on. I'm looking for a nice script solution.

Update 2

By Fast, I mean fast to implement...not necessarily fast to run.

回答1:

Here's a PowerShell example:

gc file.txt | select -Skip 2 | % { $_.ToCharArray() } | sort -CaseSensitive -Unique

which produces:

D
Y
a
b
o

I like that it's easy to read.

EDIT: Here's a faster version:

$letters = @{} ; gc file.txt | select -Skip 2 | % { $_.ToCharArray() } | % { $letters[$_] = $true } ; $letters.Keys

回答2:

BASH shell script version (no sed/awk):

while read -n 1 char; do echo "$char"; done < entry.txt | tr [A-Z] [a-z] |  sort -u

UPDATE: Just for the heck of it, since I was bored and still thinking about this problem, here's a C++ version using set. If run time is important this would be my recommended option, since the C++ version takes slightly more than half a second to process a file with 450,000+ entries.

#include <iostream>
#include <set>

int main() {
    std::set<char> seen_chars;
    std::set<char>::const_iterator iter;
    char ch;

    /* ignore whitespace and case */
    while ( std::cin.get(ch) ) {
        if (! isspace(ch) ) {
            seen_chars.insert(tolower(ch));
        }
    }

    for( iter = seen_chars.begin(); iter != seen_chars.end(); ++iter ) {
        std::cout << *iter << std::endl;
    }

    return 0;
}

Note that I'm ignoring whitespace and it's case insensitive as requested.

For a 450,000+ entry file (chars.txt), here's a sample run time:

[user@host]$ g++ -o unique_chars unique_chars.cpp 
[user@host]$ time ./unique_chars < chars.txt
a
b
d
o
y

real    0m0.638s
user    0m0.612s
sys     0m0.017s

回答3:

As requested, a pure shell-script "solution":

sed -e "s/./\0\n/g" inputfile | sort -u

It's not nice, it's not fast and the output is not exactly as specified, but it should work ... mostly.

For even more ridiculousness, I present the version that dumps the output on one line:

sed -e "s/./\0\n/g" inputfile | sort -u | while read c; do echo -n "$c" ; done

回答4:

Use a set data structure. Most programming languages / standard libraries come with one flavour or another. If they don't, use a hash table (or generally, dictionary) implementation and just omit the value field. Use your characters as keys. These data structures generally filter out duplicate entries (hence the name set, from its mathematical usage: sets don't have a particular order and only unique values).

回答5:

Quick and dirty C program that's blazingly fast:

#include <stdio.h>

int main(void)
{
  int chars[256] = {0}, c;
  while((c = getchar()) != EOF)
    chars[c] = 1;
  for(c = 32; c < 127; c++)  // printable chars only
  {
    if(chars[c])
      putchar(c);
  }

  putchar('\n');

  return 0;
}

Compile it, then do

cat file | ./a.out

To get a list of the unique printable characters in file.

回答6:

Python w/sets (quick and dirty)

s = open("data.txt", "r").read()
print "Unique Characters: {%s}" % ''.join(set(s))

Python w/sets (with nicer output)

import re

text = open("data.txt", "r").read().lower()
unique = re.sub('\W, '', ''.join(set(text))) # Ignore non-alphanumeric

print "Unique Characters: {%s}" % unique

回答7:

A very fast solution would be to make a small C program that reads its standard input, does the aggregation and spits out the result.

Why the arbitrary limitation that you need a "script" that does it?

What exactly is a script anyway?

Would Python do?

If so, then this is one solution:

import sys;

s = set([]);
while True:
    line = sys.stdin.readline();
    if not line:
        break;
    line = line.rstrip();
    for c in line.lower():
        s.add(c);

print("".join(sorted(s)));

回答8:

Algorithm: Slurp the file into memory.

Create an array of unsigned ints, initialized to zero.

Iterate though the in memory file, using each byte as a subscript into the array.
    increment that array element.

Discard the in memory file

Iterate the array of unsigned int
       if the count is not zero,
           display the character, and its corresponding count.

回答9:

cat yourfile | 
 perl -e 'while(<>){chomp;$k{$_}++ for split(//, lc $_)}print keys %k,"\n";'

回答10:

Alternative solution using bash:

sed "s/./\l\0\n/g" inputfile | sort -u | grep -vc ^$

EDIT Sorry, I actually misread the question. The above code counts the unique characters. Just omitting the c switch at the end obviously does the trick but then, this solution has no real advantage to saua's (especially since he now uses the same sed pattern instead of explicit captures).

回答11:

While not an script this java program will do the work. It's easy to understand an fast ( to run )

import java.util.*;
import java.io.*;
public class  Unique {
    public static void main( String [] args ) throws IOException { 
        int c = 0;
        Set s = new TreeSet();
        while( ( c = System.in.read() ) > 0 ) {
            s.add( Character.toLowerCase((char)c));
        }
        System.out.println( "Unique characters:" + s );
    }
}

You'll invoke it like this:

type yourFile | java Unique

or

cat yourFile | java Unique

For instance, the unique characters in the HTML of this question are:

Unique characters:[ , , ,  , !, ", #, $, %, &, ', (, ), +, ,, -, ., /, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, :, ;, <, =, >, ?, @, [, \, ], ^, _, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, {, |, }]

回答12:

in c++ i would first loop through the letters in the alphabet then run a strchr() on each with the file as a string. this will tell you if that letter exists, then just add it to the list.

回答13:

Try this file with JSDB Javascript (includes the javascript engine in the Firefox browser):

var seenAlreadyMap={};
var seenAlreadyArray=[];
while (!system.stdin.eof)
{
  var L = system.stdin.readLine();
  for (var i = L.length; i-- > 0; )
  {
    var c = L[i].toLowerCase();
    if (!(c in seenAlreadyMap))
    {
      seenAlreadyMap[c] = true;
      seenAlreadyArray.push(c);
    }
  }
}
system.stdout.writeln(seenAlreadyArray.sort().join(''));

回答14:

Python using a dictionary. I don't know why people are so tied to sets or lists to hold stuff. Granted a set is probably more efficient than a dictionary. However both are supposed to take constant time to access items. And both run circles around a list where for each character you search the list to see if the character is already in the list or not. Also Lists and Dictionaries are built in Python datatatypes that everyone should be using all the time. So even if set doesn't come to mind, dictionary should.

file = open('location.txt', 'r')
letters = {}
for line in file:
  if line == "":
    break
  for character in line.strip():
    if character not in letters:
      letters[character] = True
file.close()
print "Unique Characters: {" + "".join(letters.keys()) + "}"

回答15:

A C solution. Admittedly it is not the fastest to code solution in the world. But since it is already coded and can be cut and pasted, I think it counts as "fast to implement" for the poster :) I didn't actually see any C solutions so I wanted to post one for the pure sadistic pleasure :)

#include<stdio.h>

#define CHARSINSET 256
#define FILENAME "location.txt"

char buf[CHARSINSET + 1];

char *getUniqueCharacters(int *charactersInFile) {
    int x;
    char *bufptr = buf;
    for (x = 0; x< CHARSINSET;x++) {
        if (charactersInFile[x] > 0)
            *bufptr++ = (char)x;
    }
    bufptr = '\0';
    return buf;
}

int main() {
    FILE *fp;
    char c;
    int *charactersInFile = calloc(sizeof(int), CHARSINSET);
    if (NULL == (fp = fopen(FILENAME, "rt"))) {
        printf ("File not found.\n");
        return 1;
    }
    while(1) {
        c = getc(fp);
        if (c == EOF) {
            break;
        }
        if (c != '\n' && c != '\r')
            charactersInFile[c]++;
    }

    fclose(fp);
    printf("Unique characters: {%s}\n", getUniqueCharacters(charactersInFile));
    return 0;
}

回答16:

Quick and dirty solution using grep (assuming the file name is "file"):

for char in a b c d e f g h i j k l m n o p q r s t u v w x y z; do 
    if [ ! -z "`grep -li $char file`" ]; then 
        echo -n $char; 
    fi; 
done; 
echo

I could have made it a one-liner but just want to make it easier to read.

(EDIT: forgot the -i switch to grep)

回答17:

Well my friend, I think this is what you had in mind....At least this is the python version!!!

f = open("location.txt", "r") # open file

ll = sorted(list(f.read().lower())) #Read file into memory, split into individual characters, sort list
ll = [val for idx, val in enumerate(ll) if (idx == 0 or val != ll[idx-1])] # eliminate duplicates
f.close()
print "Unique Characters: {%s}" % "".join(ll) #print list of characters, carriage return will throw in a return

It does not iterate through each character, it is relatively short as well. You wouldn't want to open a 500 MB file with it (depending upon your RAM) but for shorter files it is fun :)

I also have to add my final attack!!!! Admittedly I eliminated two lines by using standard input instead of a file, I also reduced the active code from 3 lines to 2. Basically if I replaced ll in the print line with the expression from the line above it, I could have had 1 line of active code and one line of imports.....Anyway now we are having fun :)

import itertools, sys

# read standard input into memory, split into characters, eliminate duplicates
ll = map(lambda x:x[0], itertools.groupby(sorted(list(sys.stdin.read().lower()))))
print "Unique Characters: {%s}" % "".join(ll) #print list of characters, carriage return will throw in a return

回答18:

This answer above mentioned using a dictionary.

If so, the code presented there can be streamlined a bit, since the Python documentation states:

It is best to think of a dictionary as an unordered set of key: value pairs, with the requirement that the keys are unique (within one dictionary).... If you store using a key that is already in use, the old value associated with that key is forgotten.

Therefore, this line of the code can be removed, since the dictionary keys will always be unique anyway:

    if character not in letters:

And that should make it a little faster.

回答19:

Where C:/data.txt contains 454,863 rows of seven random alphabetic characters, the following code

using System;
using System.IO;
using System.Collections;
using System.Diagnostics;

namespace ConsoleApplication {
    class Program {
        static void Main(string[] args) {
            FileInfo fileInfo = new FileInfo(@"C:/data.txt");
            Console.WriteLine(fileInfo.Length);

            Stopwatch sw = new Stopwatch();
            sw.Start();

            Hashtable table = new Hashtable();

            StreamReader sr = new StreamReader(@"C:/data.txt");
            while (!sr.EndOfStream) {
                char c = Char.ToLower((char)sr.Read());
                if (!table.Contains(c)) {
                    table.Add(c, null);
                }
            }
            sr.Close();

            foreach (char c in table.Keys) {
                Console.Write(c);
            }
            Console.WriteLine();

            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
        }
    }
}

produces output

4093767
mytojevqlgbxsnidhzupkfawr
c
889
Press any key to continue . . .

The first line of output tells you the number of bytes in C:/data.txt (454,863 * (7 + 2) = 4,093,767 bytes). The next two lines of output are the unique characters in C:/data.txt (including a newline). The last line of output tells you the number of milliseconds the code took to execute on a 2.80 GHz Pentium 4.

回答20:

s=open("text.txt","r").read()
l= len(s)
unique ={}
for i in range(l):
 if unique.has_key(s[i]):
  unique[s[i]]=unique[s[i]]+1
 else:
  unique[s[i]]=1
print unique

回答21:

Python without using a set.

file = open('location', 'r')

letters = []
for line in file:
    for character in line:
        if character not in letters:
            letters.append(character)

print(letters)

回答22:

Print unique characters (ASCII and Unicode UTF-8)

import codecs
file = codecs.open('my_file_name', encoding='utf-8')

# Runtime: O(1)
letters = set()

# Runtime: O(n^2)
for line in file:
  for character in line:
    letters.add(character)

# Runtime: O(n)
letter_str = ''.join(letters)

print(letter_str)

Save as unique.py, and run as python unique.py.