views:

1652

answers:

8

Hi,

I'm a non-computer science student doing a history thesis that involves determining the frequency of specific terms in a number of texts and then plotting these frequencies over time to determine changes and trends. While I have figured out how to determine word frequencies for a given text file, I am dealing with a (relatively, for me) large number of files (>100) and for consistencies sake would like to limit the words included in the frequency count to a specific set of terms (sort of like the opposite of a "stop list")

This should be kept very simple. At the end all I need to have is the frequencies for the specific words for each text file I process, preferably in spreadsheet format (tab delineated file) so that I can then create graphs and visualizations using that data.

While I am not a programmer I do use linux day-to-day, am comfortable using the command line, and would love an open-source solution (or something I could run with WINE). That is not a requirement however:

I see two ways to solve this problem:

  1. Find a way strip-out all the words in a text file EXCEPT for the pre-defined list and then do the frequency count from there, or:
  2. Find a way to do a frequency count using just the terms from the pre-defined list.

Any Ideas? Thanks for your Time, Frank

+1  A: 

I'm guessing that new files get introduced over time, and that's how things change?

I reckon your best bet would be to go with something like your option 2. There's not much point pre-processing the files, if all you want to do is count occurrences of keywords. I'd just go through each file once, counting each time a word in your list appears. Personally I'd do it in Ruby, but a language like perl or python would also make this task pretty straightforward. E.g., you could use an associative array with the keywords as the keys, and a count of occurrences as the values. (But this might be too simplistic if you need to store more information about the occurrences).

I'm not sure if you want to store information per file, or about the whole dataset? I guess that wouldn't be too hard to incorporate.

I'm not sure about what to do with the data once you've got it -- exporting it to a spreadsheet would be fine, if that gives you what you need. Or you might find it easier in the long-run just to write a bit of extra code that displays the data nicely for you. Depends on what you want to do with the data (e.g. if you want to produce just a few charts at the end of the exercise and put them into a report, then exporting to CSV would probably make most sense, whereas if you want to generate a new set of data every day for a year then building a tool to do that automatically is almost certainly the best idea.

Edit: I just figured out that since you're studying history, the chances are your documents are not changing over time, but rather reflect a set of changes that happened already. Sorry for misunderstanding that. Anyway, I think pretty much everything I said above still applies, but I guess you'll lean towards going with exporting to CSV or what have you rather than an automated display.

Sounds like a fun project -- good luck!

Ben

Ben
+6  A: 

I would go with the second idea. Here is a simple Perl program that will read a list of words from the first file provided and print a count of each word in the list from the second file provided in tab-separated format. The list of words in the first file should be provided one per line.

#!/usr/bin/perl

use strict;
use warnings;

my $word_list_file = shift;
my $process_file = shift;

my %word_counts;

# Open the word list file, read a line at a time, remove the newline,
# add it to the hash of words to track, initialize the count to zero
open(WORDS, $word_list_file) or die "Failed to open list file: $!\n";
while (<WORDS>) {
  chomp;
  # Store words in lowercase for case-insensitive match
  $word_counts{lc($_)} = 0;
}
close(WORDS);

# Read the text file one line at a time, break the text up into words
# based on word boundaries (\b), iterate through each word incrementing
# the word count in the word hash if the word is in the hash
open(FILE, $process_file) or die "Failed to open process file: $!\n";

while (<FILE>) {
  chomp;
  while ( /-$/ ) {
    # If the line ends in a hyphen, remove the hyphen and
    # continue reading lines until we find one that doesn't
    chop;
    my $next_line = <FILE>;
    defined($next_line) ? $_ .= $next_line : last;
  }

  my @words = split /\b/, lc; # Split the lower-cased version of the string
  foreach my $word (@words) {
    $word_counts{$word}++ if exists $word_counts{$word};
  }
}
close(FILE);

# Print each word in the hash in alphabetical order along with the
# number of time encountered, delimited by tabs (\t)
foreach my $word (sort keys %word_counts)
{
  print "$word\t$word_counts{$word}\n"
}

If the file words.txt contains:

linux
frequencies
science
words

And the file text.txt contains the text of your post, the following command:

perl analyze.pl words.txt text.txt

will print:

frequencies     3
linux   1
science 1
words   3

Note that breaking on word boundaries using \b may not work the way you want in all cases, for example, if your text files contain words that are hyphenated across lines you will need to do something a little more intelligent to match these. In this case you could check to see if the last character in a line is a hyphen and, if it is, just remove the hyphen and read another line before splitting the line into words.

Edit: Updated version that handles words case-insensitively and handles hyphenated words across lines.

Note that if there are hyphenated words, some of which are broken across lines and some that are not, this won't find them all because it only removed hyphens at the end of a line. In this case you may want to just remove all hyphens and match words after the hyphens are removed. You can do this by simply adding the following line right before the split function:

s/-//g;
Robert Gamble
Brilliant. Thank you so much!
fdsayre
Thanks for the edit. I am thinking I will need to clean up the text first, removing hyphenation, caps, etc. to make the data more consistent before doing frequency count. One last question: Is there a way to output the command to a tab delineated file? if not its easy to cut and paste. THANKS.
fdsayre
I will edit the program to handle words case-insensitively and handle hyphenated words properly. You can redirect the output to a file like this: analyze.pl file1 file2 > file3.
Robert Gamble
final question: Is there any simple way to deal with two word terms? I.E. If the term definition file contains the phrase "normal curve" will it be counted. I'm very impressed that this script returns a 0 when the term isn't present in the text as this will make it easier to keep data consistent.
fdsayre
@fdsayre: The current algorithm is obviously geared toward one word terms. There are a couple of ways to handle this without completely changing the algorithm but the ones that comes to mind aren't very simple.
Robert Gamble
@fdsayre: If your files and word lists aren't very large, you might be able to get away with using a multiline grep utility (like mg) that you can provide a list words and ask for a count. This can become very inefficient though if the word lists or search text is large.
Robert Gamble
Okay,thank you. I have some alternative ideas on how to handle this during the preparation stage. Probably the easiest would be to do a search and replace to joining multi-word terms and then search for the combined terms and clean up the resulting data after.
fdsayre
+1  A: 

First familiarize yourself with lexical analysis and how to write a scanner generator specification. Read the introductions to using tools like YACC, Lex, Bison, or my personal favorite, JFlex. Here you define what constitutes a token. This is where you learn about how to create a tokenizer.

Next you have what is called a seed list. The opposite of the stop list is usually referred to as the start list or limited lexicon. Lexicon would also be a good thing to learn about. Part of the app needs to load the start list into memory so it can be quickly queried. The typical way to store is a file with one word per line, then read this in at the start of the app, once, into something like a map. You might want to learn about the concept of hashing.

From here you want to think about the basic algorithm and the data structures necessary to store the result. A distribution is easily represented as a two dimensional sparse array. Learn the basics of a sparse matrix. You don't need 6 months of linear algebra to understand what it does.

Because you are working with larger files, I would advocate a stream-based approach. Don't read in the whole file into memory. Read it as a stream into the tokenizer that produces a stream of tokens.

In the next part of the algorithm think about how to transform the token list into a list containing only the words you want. If you think about it, the list is in memory and can be very large, so it is better to filter out non-start-words at the start. So at the critical point where you get a new token from the tokenizer and before adding it to the token list, do a lookup in the in-memory start-words-list to see if the word is a start word. If so, keep it in the output token list. Otherwise ignore it and move to the next token until the whole file is read.

Now you have a list of tokens only of interest. The thing is, you are not looking at other indexing metrics like position and case and context. Therefore, you really don't need a list of all tokens. You really just want a sparse matrix of distinct tokens with associated counts.

So,first create an empty sparse matrix. Then think about the insertion of the newly found token during parsing. When it occurs, increment its count if its in the list or otherwise insert a new token with a count of 1. This time, at the end of parsing the file, you have a list of distinct tokens, each with a frequency of at least 1.

That list is now in-mem and you can do whatever you want. Dumping it to a CSV file would be a trivial process of iterating over the entries and writing each entry per line with its count.

For that matter, take a look at the non-commercial product called "GATE" or a commercial product like TextAnalyst or products listed at http://textanalysis.info

Josh
You left out vital information regarding the canonical decomposition of Unicode characters. :p
erickson
The scanner could take care of character translation, if conflation is even of interest.
Josh
+1  A: 

I'd do a "grep" on the files to find all the lines that contain your key words. (Grep -f can be used to specify an input file of words to search for (pipe the output of grep to a file). That will give you a list of lines which contain instances of your words. Then do a "sed" to replace your word separators (most likely spaces) with newlines, to give you a file of separate words (one word per line). Now run through grep again, with your same word list, except this time specify -c (to get a count of the lines with the specified words; i.e. a count of the occurrences of the word in the original file).

The two-pass method simply makes life easier for "sed"; the first grep should eliminate a lot of lines.

You can do this all in basic linux command-line commands. Once you're comfortable with the process, you can put it all into shell script pretty easily.

McWafflestix
+3  A: 

I do this sort of thing with a script like following (in bash syntax):

for file in *.txt
do 
  sed -r 's/([^ ]+) +/\1\n/g' "$file" \
  | grep -F -f 'go-words' \
  | sort | uniq -c > "${file}.frq"
done

You can tweak the regex you use to delimit individual words; in the example I just treat whitespace as the delimiter. The -f argument to grep is a file that contains your words of interest, one per line.

erickson
+1  A: 

Another Perl attempt:

#!/usr/bin/perl -w
use strict;

use File::Slurp;
use Tie::File;

# Usage:
#
# $ perl WordCount.pl <Files>
# 
# Example:
# 
# $ perl WordCount.pl *.text
#
# Counts words in all files given as arguments.
# The words are taken from the file "WordList".
# The output is appended to the file "WordCount.out" in the format implied in the
# following example:
#
# File,Word1,Word2,Word3,...
# File1,0,5,3,...
# File2,6,3,4,...
# .
# .
# .
# 

### Configuration

my $CaseSensitive = 1;       # 0 or 1
my $OutputSeparator = ",";   # another option might be "\t" (TAB)
my $RemoveHyphenation = 0;   # 0 or 1.  Careful, may be too greedy.

###

my @WordList = read_file("WordList");
chomp @WordList;

tie (my @Output, 'Tie::File', "WordCount.out");
push (@Output, join ($OutputSeparator, "File", @WordList));

for my $InFile (@ARGV)
    { my $Text = read_file($InFile);
      if ($RemoveHyphenation) { $Text =~ s/-\n//g; };
      my %Count;
      for my $Word (@WordList)
          { if ($CaseSensitive)
               { $Count{$Word} = ($Text =~ s/(\b$Word\b)/$1/g); }
               else
               { $Count{$Word} = ($Text =~ s/(\b$Word\b)/$1/gi); }; };
      my $OutputLine = "$InFile";
      for my $Word (@WordList)
          { if ($Count{$Word})
               { $OutputLine .= $OutputSeparator . $Count{$Word}; }
               else
               { $OutputLine .= $OutputSeparator . "0"; }; };
      push (@Output, $OutputLine); };

untie @Output;

When I put your question in the file wc-test and Robert Gamble's answer into wc-ans-test, the Output file looks like this:

File,linux,frequencies,science,words
wc-ans-test,2,2,2,12
wc-test,1,3,1,3

This is a comma separated value (csv) file (but you can change the separator in the script). It should be readable for any spreadsheet application. For plotting graphs, I would recommend gnuplot, which is fully scriptable, so you can tweak your output independently of the input data.

Svante
thank you, this looks good. I will run it against my test data and see what results.
fdsayre
+1  A: 

To hell with big scripts. If you're willing to grab all words, try this shell fu:

cat *.txt | tr A-Z a-z | tr -cs a-z '\n' | sort | uniq -c | sort -rn | 
sed '/[0-9] /&, /'

That (tested) will give you a list of all words sorted by frequency in CSV format, easily imported by your favorite spreadsheet. If you must have the stop words then try inserting grep -w -F -f stopwords.txt into the pipeline (not tested).

Norman Ramsey
A: 

can anyone give an answer to the same question in c# or c++