#!/usr/bin/python
import sys
import codecs
import re

def calculate_g0_dice(ngram_frequency_distr,unigram_frequency_distr):
	result=[]
	for ngram in ngram_frequency_distr:
		if ngram_frequency_distr[ngram]>=min_frequency: #minimum frequency
			result.append((float(ngram_length)*ngram_frequency_distr[ngram]/sum([unigram_frequency_distr[e] for e in ngram]),ngram))
	return sorted(result,reverse=True)

def calculate_g0_mi(ngram_frequency_distr,unigram_frequency_distr):
	result=[]
	ngram_probability=relativize_distr(ngram_frequency_distr)
	unigram_probability=relativize_distr(unigram_frequency_distr)
	from math import log
	for ngram in ngram_probability:
		if ngram_frequency_distr[ngram]>=min_frequency: # minimum frequency
			#result.append((log(ngram_frequency_distr[ngram]*ngram_probability[ngram]/product([unigram_probability[e] for e in ngram])),ngram))
			result.append(((log(ngram_probability[ngram]/product([unigram_probability[e] for e in ngram]))),ngram))
	return sorted(result,reverse=True)

def calculate_g0_ll(ngram_frequency):
	result=[]
	from math import log
	observed_functions=[observed2,observed3,observed4]
	expected_functions=[expected2,expected3,expected4]
	for ngram in lemma_token_frequency_distr:
		if ngram_frequency[ngram]>=min_frequency:
			marginals=[ngram_frequency[e] for e in create_ngram_star(ngram)]
			observed=observed_functions[ngram_length-2](marginals)
			expected=expected_functions[ngram_length-2](observed)
			ll=0.0
			for o,e in zip(observed,expected):
				try:
					ll+=o*log(o/e)
				except:
					pass
			result.append((2*ll,ngram))
	return sorted(result,reverse=True)

def calculate_g0_chisq(ngram_frequency):
	result=[]
	observed_functions=[observed2,observed3,observed4]
	expected_functions=[expected2,expected3,expected4]
	for ngram in lemma_token_frequency_distr:
		if ngram_frequency[ngram]>=min_frequency:
			marginals=[ngram_frequency[e] for e in create_ngram_star(ngram)]
			observed=observed_functions[ngram_length-2](marginals)
			expected=expected_functions[ngram_length-2](observed)
			chisq=0.0
			for o,e in zip(observed,expected):
				try:
					chisq+=(o-e)**2/e
				except:
					pass
			result.append((chisq,ngram))
	return sorted(result,reverse=True)

def calculate_g0_tscore(ngram_frequency):
	from math import sqrt
	result=[]
	observed_functions=[observed2,observed3,observed4]
	expected_functions=[expected2,expected3,expected4]
	for ngram in lemma_token_frequency_distr:
		if ngram_frequency[ngram]>=min_frequency:
			marginals=[ngram_frequency[e] for e in create_ngram_star(ngram)]
			observed=observed_functions[ngram_length-2](marginals)
			expected=expected_functions[ngram_length-2](observed)
			tscore=float(observed[0]-expected[0])/sqrt(expected[0])
			result.append((tscore,ngram))
	return sorted(result,reverse=True)

def observed2(marginals):
	n_ii,n_ix,n_xi,n_xx=marginals
	n_oi = n_xi - n_ii
	n_io = n_ix - n_ii
	return (n_ii, n_io, n_oi, n_xx - n_ii - n_oi - n_io)

def expected2(observed):
	n_ii, n_io, n_oi, n_oo=observed
	n_xx = float(n_ii+n_oi+n_io+n_oo)
	e_ii=(n_ii+n_io)*(n_ii+n_oi)/n_xx
	e_io=(n_ii+n_io)*(n_io+n_oo)/n_xx
	e_oi=(n_oi+n_oo)*(n_ii+n_oi)/n_xx
	e_oo=(n_oi+n_oo)*(n_io+n_oo)/n_xx
	return (e_ii,e_io,e_oi,e_oo) 
	
def expected_nltk(contingency):
	n_xx=sum(contingency)
	for i in range(4): 
		yield (contingency[i] + contingency[i ^ 1]) * (contingency[i] + contingency[i ^ 2]) / float(n_xx)

def observed3(marginals):
	n_iii,n_iix,n_ixi,n_ixx,n_xii,n_xix,n_xxi,n_xxx=marginals
	n_oii = n_xii - n_iii
	n_ioi = n_ixi - n_iii 
	n_iio = n_iix - n_iii 
	n_ooi = n_xxi - n_iii - n_oii - n_ioi
	n_oio = n_xix - n_iii - n_oii - n_iio 
	n_ioo = n_ixx - n_iii - n_ioi - n_iio 
	n_ooo = n_xxx - n_iii - n_oii - n_ioi - n_iio - n_ooi - n_oio - n_ioo 
	return (n_iii, n_iio, n_ioi, n_oii, n_ioo, n_ooi, n_oio, n_ooo)

def expected3(observed):
	o_iii, o_iio, o_ioi, o_oii, o_ioo, o_ooi, o_oio, o_ooo=observed
	n_xxx=float(o_iii+o_iio+o_ioi+o_oii+o_ioo+o_ooi+o_oio+o_ooo)
	e_iii=(o_iii+o_oii)*(o_iii+o_ioi)*(o_iii+o_iio)/n_xxx
	e_iio=(o_iio+o_oio)*(o_iio+o_ioi)*(o_iio+o_iii)/n_xxx
	e_ioi=(o_ioi+o_ooi)*(o_ioi+o_iii)*(o_ioi+o_ioo)/n_xxx
	e_oii=(o_oii+o_iii)*(o_oii+o_ooi)*(o_oii+o_oio)/n_xxx
	e_ioo=(o_ioo+o_ooo)*(o_ioo+o_iio)*(o_ioo+o_ioi)/n_xxx
	e_ooi=(o_ooi+o_ioi)*(o_ooi+o_oii)*(o_ooi+o_ooo)/n_xxx
	e_oio=(o_oio+o_iio)*(o_oio+o_ooo)*(o_oio+o_oii)/n_xxx
	e_ooo=(o_ooo+o_ioo)*(o_ooo+o_oio)*(o_ooo+o_ooi)/n_xxx
	return (e_iii,e_iio,e_ioi,e_oii,e_ioo,e_ooi,e_oio,e_ooo)

def observed4(marginals):
	n_iiii,n_xiii,n_ixii,n_iixi,n_iiix,n_xxii,n_ixxi,n_iixx,n_xixi,n_xiix,n_ixix,n_xxxi,n_xxix,n_xixx,n_ixxx,n_xxxx=marginals
	o_iiii=n_iiii
	o_oiii=n_xiii-n_iiii
	o_ioii=n_ixii-n_iiii
	o_iioi=n_iixi-n_iiii
	o_iiio=n_iiix-n_iiii
	o_ooii=n_xxii-n_iiii-o_oiii-o_ioii
	o_iooi=n_ixxi-n_iiii-o_ioii-o_iioi
	o_iioo=n_iixx-n_iiii-o_iioi-o_iiio
	o_oioi=n_xixi-n_iiii-o_oiii-o_iioi
	o_ioio=n_ixix-n_iiii-o_ioii-o_iiio
	o_oiio=n_ixxi-n_iiii-o_ioii-o_iioi
	o_oooi=n_xxxi-n_iiii-o_oiii-o_ioii-o_iioi-o_ooii-o_oioi-o_iooi
	o_ooio=n_xxix-n_iiii-o_oiii-o_ioii-o_iiio-o_ooii-o_oiio-o_ioio
	o_oioo=n_xixx-n_iiii-o_oiii-o_iioi-o_iiio-o_oioi-o_iioo-o_oiio
	o_iooo=n_ixxx-n_iiii-o_ioii-o_iioi-o_iiio-o_iooi-o_iioo-o_ioio
	o_oooo=n_xxxx-n_iiii-o_oiii-o_ioii-o_iioi-o_iiio-o_ooii-o_iooi-o_iioo-o_oioi-o_ioio-o_oiio-o_oooi-o_ooio-o_oioo-o_iooo
	return (o_iiii,o_oiii,o_ioii,o_iioi,o_iiio,o_ooii,o_iooi,o_iioo,o_oioi,o_ioio,o_oiio,o_oooi,o_ooio,o_oioo,o_iooo,o_oooo)

def expected4(observed):
	o_iiii,o_oiii,o_ioii,o_iioi,o_iiio,o_ooii,o_iooi,o_iioo,o_oioi,o_ioio,o_oiio,o_oooi,o_ooio,o_oioo,o_iooo,o_oooo=observed
	n_xxxx=float(o_iiii+o_oiii+o_ioii+o_iioi+o_iiio+o_ooii+o_iooi+o_iioo+o_oioi+o_ioio+o_oiio+o_oooi+o_ooio+o_oioo+o_iooo+o_oooo)
	e_iiii=(o_iiii+o_oiii)*(o_iiii+o_ioii)*(o_iiii+o_iioi)*(o_iiii+o_iiio)/n_xxxx
	e_oiii=(o_oiii+o_iiii)*(o_oiii+o_ooii)*(o_oiii+o_oioi)*(o_oiii+o_oiio)/n_xxxx
	e_ioii=(o_ioii+o_ooii)*(o_ioii+o_iiii)*(o_ioii+o_iooi)*(o_ioii+o_ioio)/n_xxxx
	e_iioi=(o_iioi+o_oioi)*(o_iioi+o_iooi)*(o_iioi+o_iiii)*(o_iioi+o_iioo)/n_xxxx
	e_iiio=(o_iiio+o_oiio)*(o_iiio+o_ioio)*(o_iiio+o_iioo)*(o_iiio+o_iiii)/n_xxxx
	e_ooii=(o_ooii+o_ioii)*(o_ooii+o_oiii)*(o_ooii+o_oooi)*(o_ooii+o_ooio)/n_xxxx
	e_oioi=(o_oioi+o_iioi)*(o_oioi+o_oooi)*(o_oioi+o_oiii)*(o_oioi+o_oioo)/n_xxxx
	e_oiio=(o_oiio+o_iiio)*(o_oiio+o_ooio)*(o_oiio+o_oioo)*(o_oiio+o_oiii)/n_xxxx
	e_iooi=(o_iooi+o_oooi)*(o_iooi+o_iioi)*(o_iooi+o_ioii)*(o_iooi+o_iooo)/n_xxxx
	e_ioio=(o_ioio+o_ooio)*(o_ioio+o_iiio)*(o_ioio+o_iooo)*(o_ioio+o_ioii)/n_xxxx
	e_iioo=(o_iioo+o_oioo)*(o_iioo+o_iooo)*(o_iioo+o_iiio)*(o_iioo+o_iioi)/n_xxxx
	e_oooi=(o_oooi+o_iooi)*(o_oooi+o_oioi)*(o_oooi+o_ooii)*(o_oooi+o_oooo)/n_xxxx
	e_ooio=(o_ooio+o_ioio)*(o_ooio+o_oiio)*(o_ooio+o_oooo)*(o_ooio+o_ooii)/n_xxxx
	e_oioo=(o_oioo+o_iioo)*(o_oioo+o_oooo)*(o_oioo+o_oiio)*(o_oioo+o_oioi)/n_xxxx
	e_iooo=(o_iooo+o_oooo)*(o_iooo+o_iioo)*(o_iooo+o_ioio)*(o_iooo+o_iooi)/n_xxxx
	e_oooo=(o_oooo+o_iooo)*(o_oooo+o_oioo)*(o_oooo+o_ooio)*(o_oooo+o_oooi)/n_xxxx
	return (e_iiii,e_oiii,e_ioii,e_iioi,e_iiio,e_ooii,e_iooi,e_iioo,e_oioi,e_ioio,e_oiio,e_oooi,e_ooio,e_oioo,e_iooo,e_oooo)

def create_ngram_star(lemmas):
	from itertools import product
	ngrams=[]
	for logical_vector in product((True,False),repeat=ngram_length):
		logical_ngram=['*' for e in range(ngram_length)]
		for index,logical_value in enumerate(logical_vector):
			if logical_value:
				logical_ngram[index]=lemmas[index]
		ngrams.append(tuple(logical_ngram))
	return ngrams

product=lambda s: reduce(lambda x, y: x * y, s)

def avg_idf(ngram):
	max_idf=max(idf.values())
	
	avg_idf=0.0
	for lemma in ngram:
		avg_idf+=idf.get(lemma,max_idf)
	return avg_idf/len(ngram)

def calculate_tfidf(ngram_frequency_distr):
	result=[]
	ngram_probability=relativize_distr(ngram_frequency_distr)
	for ngram,tf in ngram_probability.iteritems():
		if ngram_frequency_distr[ngram]>=min_frequency:
			idf_avg=0.0
			result.append((tf*avg_idf(ngram),ngram))
	return sorted(result,reverse=True)

def relativize_distr(distr):
	copy_distr={}
	all=float(sum(distr.values()))
	for key,value in distr.iteritems():
		copy_distr[key]=distr[key]/all
	return copy_distr

min_frequency=3
optional_properties=set(['h','s','n','t','o','pos','prop','min','idf','seq','norm','terms'])
mandatory_properties=set(['i','p','m','l'])
definable_properties=optional_properties.union(mandatory_properties)
properties={}
ranking_methods={'dice':calculate_g0_dice,'mi':calculate_g0_mi,'ll':calculate_g0_ll,'chisq':calculate_g0_chisq,'tscore':calculate_g0_tscore,'tfidf':calculate_tfidf}

def parse_arguments():
	key=None
	for argument in sys.argv[1:]:
		if argument.startswith('-'):
			key=argument[1:]
			if key=='h':
				print_help()
			if key not in definable_properties:
				sys.stderr.write('Warning: argument identifier '+argument+' unknown\n')
			else:
				properties[key]=[]
		elif key is None:
			sys.stderr.write('Warning: argument '+argument+' without argument identifier'+'\n')
		elif key in definable_properties:
			properties[key].append(argument)
		else:
			sys.stderr.write('Error: unknown argument identifier '+key+'\n')
			print_help()

def print_help():
	sys.stderr.write('Syntax:\n')
	sys.stderr.write('python CollTerm.py -i input_file -p phrase_configuration_file -m ngram_ranking_method -l length_of_ngrams\n')
	sys.stderr.write('Arguments:\n')
	sys.stderr.write('-i\ttab separated input file\n')
	sys.stderr.write('-p\tphrase configuration file\n')
	sys.stderr.write('\t\t- symbols for defining stop word phrases:\n')
	sys.stderr.write('\t\t\t- !STOP - non-stop word\n')
	sys.stderr.write('\t\t\t- STOP - stop word\n')
	sys.stderr.write('\t\t\t- * - any word\n')
	sys.stderr.write('\t\t- bigram example: STOP	*\n')
	sys.stderr.write('-s\tstop word file\n')
	sys.stderr.write('-n\tmaximum number of top ranked terms\n')
	sys.stderr.write('-t\tthreshold (minimum score)\n')
	sys.stderr.write('-m\tn-gram ranking method\n')
	sys.stderr.write('\t\tdice - Dice coefficient\n')
	sys.stderr.write('\t\tmi - modified mutual information\n')
	sys.stderr.write('\t\tchisq - chi-square statistic\n')
	sys.stderr.write('\t\tll - log-likelihood ratio\n')
	sys.stderr.write('\t\ttscore - t-score\n')
	sys.stderr.write('\t\ttfidf - tf-idf score (with a mandatory idf file)\n')
	sys.stderr.write('-l\tlength of n-grams to be extracted (0-4, 0 for all length n-grams)\n')
	sys.stderr.write('-o\textracted term list output file (if not given, stdout used)\n')
	sys.stderr.write('-pos\tpositions of tokens, POS tags and lemmas (zero-based indices)\n')
	sys.stderr.write('-min\tminimum frequency of n-grams taken in consideration\n')
	sys.stderr.write('-prop\tproperty file\n')
	sys.stderr.write('-idf\tidf file (mandatory for tfidf, in case of other ranking methods a linear combination is computed)\n')
	sys.stderr.write('-seq\toutput n-grams as a sequence of 0 - lemmata n-grams, 1 - most frequent token n-grams, 2 - lemmata n-grams + most frequent token n-grams, 3 - all token n-grams with their frequencies\n')
	sys.stderr.write('-norm\tnormalize output to a [0,x] range\n')
	sys.stderr.write('-terms\toutput terms as\n')
	sys.stderr.write('\t\t0 - terms and weights (+ frequency if "-seq 2")\n')
	sys.stderr.write('\t\t1 - terms only\n')
	sys.exit(1)

def check_properties():		
	global term_number
	term_number=None
	global threshold
	threshold=None
	global ranking_method
	global ngram_length
	global output_file
	global position
	global min_frequency
	global seq
	seq=0
	global norm
	norm=0
	global terms
	terms=0
	# -prop
	if 'prop' in properties:
		if properties['prop']==[]:
			sys.stderr.write('Error: no argument given for property file (-prop)\n')
			print_help()
		import re
		line_re=re.compile('(.+?)=(.+)')
		try:
			properties_file=open(properties['prop'][-1])
		except:
			sys.stderr.write('Error: can not open property file (-prop): '+properties['prop'][-1]+'\n')
			print_help()
		i=0
		for line in properties_file:
			i+=1
			if line.strip().startswith('#'):
				continue
			result=line_re.search(line)
			if result is None:
				sys.stderr.write('Error in property file line '+str(i)+'\n'+repr(line)+'\n') 
				print_help()
			key=result.group(1).strip()
			if '"' in line:
				values=re.findall(r'"(.+?)"',result.group(2).strip())
			else:
				values=re.split(r'\s+',result.group(2).strip())
			if key not in definable_properties:
				sys.stderr.write('Error: unknown argument identifier '+key+' (property file)\n')
				print_help()
			properties[key]=values
	missing_properties=mandatory_properties.difference(mandatory_properties.intersection(properties))
	if len(missing_properties)>0:
		sys.stderr.write('Error: these mandatory properties are missing: '+', '.join(missing_properties)+'\n')
		print_help()

	# -n
	if 'n' in properties:
		if properties['n']==[]:
			sys.stderr.write('Error: no argument given for number of terms (-n)\n')
			print_help()		
		try:
			term_number=int(properties['n'][-1])
		except:
			sys.stderr.write('Error: wrong argument for number of terms (-n): '+properties['n'][-1]+'\n')
			print_help()
	# -t
	if 't' in properties:
		if properties['t']==[]:
			sys.stderr.write('Error: no argument given for threshold (-t)\n')
			print_help()
		try:
			threshold=float(properties['t'][-1])
		except:
			sys.stderr.write('Error: wrong argument for threshold (-t): '+properties['t'][-1]+'\n')
			print_help()
	# -m
	if properties['m']==[]:
		sys.stderr.write('Error: no argument given for n-gram ranking method (-m)\n')
		print_help()
	ranking_method=properties['m'][-1]
	if ranking_method not in ranking_methods:
		sys.stderr.write('Error: wrong argument for n-gram ranking method (-m): '+ranking_method+'\n')
		print_help()
	# -l
	if properties['l']==[]:
		sys.stderr.write('Error: no argument given for length of n-grams (-l)\n')
		print_help()
	try:
		ngram_length=int(properties['l'][-1])
		if ngram_length<1 or ngram_length>4:
			raise Exception
	except:
		sys.stderr.write('Error: wrong argument for length of n-grams (-l): '+properties['l'][-1]+'\n')
		print_help()
	#if ranking_method=='tfidf' and ngram_length!=1:
	#	sys.stderr.write('Error: tfidf ranking method applicable only to unigrams (-l 1)\n')
	#	print_help()
	if ngram_length==1 and 'idf' not in properties:
		sys.stderr.write('Error: idf file has to be defined for length of n-grams 1 (-l 1)\n')
		print_help()
	# -o
	if 'o' in properties:
		if properties['o']==[]:
			sys.stderr.write('Error: no argument given output file (-o)\n')
			print_help()
		try:
			output_file=open(properties['o'][-1],'w')
		except:
			sys.stderr.write('Error: can not write to output file '+properties['o'][-1]+'\n')
			print_help()	
	else:
		output_file=sys.stdout
	# -pos
	if 'pos' in properties:
		if len(properties['pos'])<3:
			sys.stderr.write('Error: wrong number of arguments given for position (-pos)\n')
			print_help()
		try:
			position=[int(e) for e in properties['pos'][-3:]]
			if len(set(position))!=3:
				raise Exception
		except:
			sys.stderr.write('Error: wrong arguments given for position (-pos): '+', '.join(properties['pos'][-3:])+'\n')
			print_help()
	else:
		position=range(3)
	# -min
	if 'min' in properties:
		if properties['min']==[]:
			sys.stderr.write('Error: no argument given for minimum frequency (-min)\n')
			print_help()
		try:
			min_frequency=int(properties['min'][-1])
		except:
			sys.stderr.write('Error: wrong argument given for minimum frequency (-min): '+properties['min'][-1]+'\n')
			print_help()
	# -idf
	if 'idf' in properties:
		if properties['idf']==[]:
			sys.stderr.write('Error: no argument given for idf file (-idf)\n')
			print_help()
	# -seq
	if 'seq' in properties:
		if properties['seq']==[]:
			sys.stderr.write('Error: no argument given for sequence output (-seq)\n')
			print_help()
		if properties['seq'][-1]!='0' and properties['seq'][-1]!='1' and properties['seq'][-1]!='2':
			sys.stderr.write('Error: wrong argument given for sequence output (-seq): '+properties['seq'][-1]+'\n')
			print_help()			
		seq=int(properties['seq'][-1])
	# -norm
	if 'norm' in properties:
		if properties['norm']==[]:
			sys.stderr.write('Error: no argument given for normalization (-norm)\n')
			print_help()
		try:
			norm=float(properties['norm'][-1])
		except:
			sys.stderr.write('Error: wrong argument given for normalization (-norm): '+properties['norm'][-1]+'\n')
			print_help()
	# -terms
	if 'terms' in properties:
		if properties['terms']==[]:
			sys.stderr.write('Error: no argument given for term output (-terms)\n')
			print_help()
		if properties['terms'][-1]!='0' and properties['terms'][-1]!='1':
			sys.stderr.write('Error: wrong argument given for term output (-terms): '+properties['terms'][-1]+'\n')
			print_help()			
		terms=int(properties['terms'][-1])

def read_phrase_configuration_file():
	global valid_phrases
	valid_phrases=[]
	global stop_phrase
	stop_phrase=[]
	global ngram_length
	if properties['p']==[]:
		sys.stderr.write('Error: no argument given for phrase configuration file (-p)\n')
		print_help()
	try:
		phrase_configuration_file=open(properties['p'][-1],'r')
	except:
		sys.stderr.write('Error: can not read phrase configuration file '+properties['p'][-1]+'\n')
		print_help()
	i=0
	for line in phrase_configuration_file:
		i+=1
		if line.strip().startswith('#'):
			continue
		if line.strip()=='':
			continue
		valid_phrase=line.strip().split('\t')
		try:
			if ngram_length!=len(valid_phrase):
				continue
			if 'STOP' in line:
				if stop_phrase!=[]:
					raise Exception
				for stop in valid_phrase:
					if stop not in ('!STOP','STOP','*'):
						raise Exception
				stop_phrase=valid_phrase
				continue
			valid_phrase=[re.compile(e) for e in valid_phrase]
		except:
			sys.stderr.write('Error in phrase configuration file line '+str(i)+'\n'+repr(line)+'\n')
			print_help()
		valid_phrases.append(valid_phrase)
	
def read_stopword_file():
	global stopwords
	stopwords=set()
	if 's' not in properties:
		return
	if properties['s']==[]:
		sys.stderr.write('Error: no argument given for stop-word file (-s)\n')
		print_help()
	try:
		stopwords=set([e.strip() for e in codecs.open(properties['s'][-1],'r','utf-8')])
	except:
		sys.stderr.write('Error: can not read stop-word file '+properties['s'][-1]+'\n')
		print_help()

def read_idf_file():
	if 'idf' not in properties:
		return
	global idf
	idf={}
	if properties['idf']==[]:
		sys.stderr.write('Error: no argument given for idf file (-idf)\n')
		print_help()
	try:
		idf=dict([(a,float(b)) for a,b in [e.split('\t') for e in codecs.open(properties['idf'][-1],'r','utf-8')]])
	except:
		sys.stderr.write('Error: can not read idf file '+properties['idf'][-1]+'\n')
		print_help()

def read_input_text():
	enamex=0
	numex=0
	timex=0
	if properties['i']==[]:
		sys.stderr.write('Error: no argument given for input file (-i)\n')
		print_help()
	path=properties['i'][-1]
	try:
		input_file=codecs.open(path,'r','utf-8')
	except:
		sys.stderr.write('Error: can not read input file '+path+'\n')
		print_help()
	i=0
	ngram=[None for e in range(ngram_length)]
	global ngram_frequency_distr
	ngram_frequency_distr={}
	global unigram_frequency_distr
	unigram_frequency_distr={}
	global lemma_token_frequency_distr
	lemma_token_frequency_distr={}
	global lemma_phrase_map
	lemma_phrase_map={}
	for line in input_file:
		if i==0:
			if line.startswith(u'\ufeff'):
				line=line[1:]
		i+=1
		split_line=line.strip().split('\t')
		if split_line==['']:
			continue
		if split_line[0][0]=='<':
			if split_line[0].startswith('<NUMEX'):
				numex+=1
			elif split_line[0].startswith('<ENAMEX'):
				enamex+=1
			elif split_line[0].startswith('<TIMEX'):
				timex+=1
			elif split_line[0].startswith('</NUMEX'):
				numex-=1
			elif split_line[0].startswith('</ENAMEX'):
				enamex-=1
			elif split_line[0].startswith('</TIMEX'):
				timex-=1
			else:
				continue
			ngram=[None for e in range(ngram_length)]
			if enamex<0 or numex<0 or timex<0:
				sys.stderr.write('Error: closing bracket without open on line '+str(i)+'\n'+repr(line)+'\n')
				sys.exit(1)
			continue
		if enamex!=0 or numex!=0 or timex!=0:
			continue
		try:
			token,pos,lemma=split_line[position[0]],split_line[position[1]],split_line[position[2]]
			token=token.lower()
			lemma=lemma.lower()
		except:
			sys.stderr.write('Error in input file line '+str(i)+'\n'+repr(line)+'\n')
			print_help()
		# actual stuff
		if ranking_method in ('dice','mi'):
			unigram_frequency_distr[lemma]=unigram_frequency_distr.get(lemma,0)+1
		ngram=ngram[1:]
		ngram.append((token,pos,lemma))
		try:
			tokens=tuple([e[0] for e in ngram])
			poses=tuple([e[1] for e in ngram])
			lemmas=tuple([e[2] for e in ngram])
		except:
			continue
		if ranking_method in ('ll','chisq','tscore'):
				for star_ngram in create_ngram_star(lemmas):
					ngram_frequency_distr[star_ngram]=ngram_frequency_distr.get(star_ngram,0)+1
		phrase=check_ngram_for_phrases(poses)
		if phrase!=None and check_ngram_for_stops(tokens):
			if lemmas not in lemma_phrase_map:
				lemma_phrase_map[lemmas]={}
			lemma_phrase_map[lemmas][phrase]=lemma_phrase_map[lemmas].get(phrase,0)+1
			if ranking_method in ('dice','mi','tfidf'):
				ngram_frequency_distr[lemmas]=ngram_frequency_distr.get(lemmas,0)+1
			if lemmas not in lemma_token_frequency_distr:
				lemma_token_frequency_distr[lemmas]={}
			lemma_token_frequency_distr[lemmas][tokens]=lemma_token_frequency_distr[lemmas].get(tokens,0)+1
	global results
	if ranking_method in ('dice','mi'):
		results=ranking_methods[ranking_method](ngram_frequency_distr,unigram_frequency_distr)
	elif ranking_method in ('ll','chisq','tscore','tfidf'):
		results=ranking_methods[ranking_method](ngram_frequency_distr)
	
def check_ngram_for_phrases(pos_ngram):
	for phrase in valid_phrases:
		valid=True
		for pos,regex in zip(pos_ngram,phrase):
			if pos is None:
				valid=False
				break
			if regex.match(pos) is None:
				valid=False
				break
		if valid:
			return ' '.join([e.pattern for e in phrase])

def check_ngram_for_stops(token_ngram):
	if stop_phrase==[]:
		return True
	for token,stop in zip(token_ngram,stop_phrase):
		if stop=='STOP' and token not in stopwords:
			return False
		elif stop=='!STOP' and token in stopwords:
			return False
	return True

def normalize_result():
	global results
	global norm
	if norm==0:
		norm=1
	values=[a for a,b in results]
	if len(values)==0:
		return
	min_value=min(values)
	max_value=max(values)
	range=float(max_value-min_value)
	for index,(value,ngram) in enumerate(results):
		try:
			results[index]=(norm*(value-min_value)/range,ngram)
		except ZeroDivisionError:
			results[index]=(norm,ngram)

def linearly_combine_with_idf():
	normalize_result()
	global results
	results=sorted([(value*0.5+avg_idf(ngram)*0.5, ngram) for value,ngram in results],reverse=True)

def output_result():
	i=0
	for value,ngram in results:
		if threshold is not None:
			if value<threshold:
				break
		if seq==0:
			output=' '.join(ngram).encode('utf-8')+'\t('+'|'.join([e[0] for e in sorted(lemma_phrase_map[ngram].items(),key=lambda x:-x[1])])+', '+str(ngram_frequency_distr[ngram])+')'
			if terms==0:
				output+='\t'+str(round(value,5))
			output_file.write(output+'\n')
		elif seq==1:
			output=' '.join(sorted(lemma_token_frequency_distr[ngram].items(),key=lambda x:x[1])[-1][0]).encode('utf-8')+'\t('+'|'.join([e[0] for e in sorted(lemma_phrase_map[ngram].items(),key=lambda x:-x[1])])+', '+str(ngram_frequency_distr[ngram])+')'
			if terms==0:
				output+='\t'+str(round(value,5))
			output_file.write(output+'\n')
		elif seq==2:
			output=' '.join(ngram).encode('utf-8')+'\t'+' '.join(sorted(lemma_token_frequency_distr[ngram].items(),key=lambda x:x[1])[-1][0]).encode('utf-8')+'\t('+'|'.join([e[0] for e in sorted(lemma_phrase_map[ngram].items(),key=lambda x:-x[1])])+', '+str(ngram_frequency_distr[ngram])+')'
			if terms==0:
				output+='\t'+str(round(value,5))
			output_file.write(output+'\n')
		else:
			for token_sequence,frequency in lemma_token_frequency_distr[ngram].iteritems():
				output=' '.join(token_sequence).encode('utf-8')+'\t('+'|'.join([e[0] for e in sorted(lemma_phrase_map[ngram].items(),key=lambda x:-x[1])])+', '+str(ngram_frequency_distr[ngram])+')'
				if terms==0:
					output+='\t'+str(frequency)+'\t'+str(round(value,5))
				output_file.write(output+'\n')
		i+=1
		if term_number is not None:
			if i>=term_number:
				break

if __name__=='__main__':
	parse_arguments()
	check_properties()
	read_phrase_configuration_file()
	read_stopword_file()
	read_idf_file()
	read_input_text()
	if ranking_method!='tfidf' and 'idf' in vars():
		linearly_combine_with_idf()
	if norm!=0:
		normalize_result()
	output_result()

cad003637271b6c4ac5419f70e12a73669dce5d7
<mask token>


def calculate_g0_mi(ngram_frequency_distr, unigram_frequency_distr):
    result = []
    ngram_probability = relativize_distr(ngram_frequency_distr)
    unigram_probability = relativize_distr(unigram_frequency_distr)
    from math import log
    for ngram in ngram_probability:
        if ngram_frequency_distr[ngram] >= min_frequency:
            result.append((log(ngram_probability[ngram] / product([
                unigram_probability[e] for e in ngram])), ngram))
    return sorted(result, reverse=True)


def calculate_g0_ll(ngram_frequency):
    result = []
    from math import log
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            ll = 0.0
            for o, e in zip(observed, expected):
                try:
                    ll += o * log(o / e)
                except:
                    pass
            result.append((2 * ll, ngram))
    return sorted(result, reverse=True)


<mask token>


def calculate_g0_tscore(ngram_frequency):
    from math import sqrt
    result = []
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            tscore = float(observed[0] - expected[0]) / sqrt(expected[0])
            result.append((tscore, ngram))
    return sorted(result, reverse=True)


def observed2(marginals):
    n_ii, n_ix, n_xi, n_xx = marginals
    n_oi = n_xi - n_ii
    n_io = n_ix - n_ii
    return n_ii, n_io, n_oi, n_xx - n_ii - n_oi - n_io


def expected2(observed):
    n_ii, n_io, n_oi, n_oo = observed
    n_xx = float(n_ii + n_oi + n_io + n_oo)
    e_ii = (n_ii + n_io) * (n_ii + n_oi) / n_xx
    e_io = (n_ii + n_io) * (n_io + n_oo) / n_xx
    e_oi = (n_oi + n_oo) * (n_ii + n_oi) / n_xx
    e_oo = (n_oi + n_oo) * (n_io + n_oo) / n_xx
    return e_ii, e_io, e_oi, e_oo


def expected_nltk(contingency):
    n_xx = sum(contingency)
    for i in range(4):
        yield (contingency[i] + contingency[i ^ 1]) * (contingency[i] +
            contingency[i ^ 2]) / float(n_xx)


def observed3(marginals):
    n_iii, n_iix, n_ixi, n_ixx, n_xii, n_xix, n_xxi, n_xxx = marginals
    n_oii = n_xii - n_iii
    n_ioi = n_ixi - n_iii
    n_iio = n_iix - n_iii
    n_ooi = n_xxi - n_iii - n_oii - n_ioi
    n_oio = n_xix - n_iii - n_oii - n_iio
    n_ioo = n_ixx - n_iii - n_ioi - n_iio
    n_ooo = n_xxx - n_iii - n_oii - n_ioi - n_iio - n_ooi - n_oio - n_ioo
    return n_iii, n_iio, n_ioi, n_oii, n_ioo, n_ooi, n_oio, n_ooo


def expected3(observed):
    o_iii, o_iio, o_ioi, o_oii, o_ioo, o_ooi, o_oio, o_ooo = observed
    n_xxx = float(o_iii + o_iio + o_ioi + o_oii + o_ioo + o_ooi + o_oio + o_ooo
        )
    e_iii = (o_iii + o_oii) * (o_iii + o_ioi) * (o_iii + o_iio) / n_xxx
    e_iio = (o_iio + o_oio) * (o_iio + o_ioi) * (o_iio + o_iii) / n_xxx
    e_ioi = (o_ioi + o_ooi) * (o_ioi + o_iii) * (o_ioi + o_ioo) / n_xxx
    e_oii = (o_oii + o_iii) * (o_oii + o_ooi) * (o_oii + o_oio) / n_xxx
    e_ioo = (o_ioo + o_ooo) * (o_ioo + o_iio) * (o_ioo + o_ioi) / n_xxx
    e_ooi = (o_ooi + o_ioi) * (o_ooi + o_oii) * (o_ooi + o_ooo) / n_xxx
    e_oio = (o_oio + o_iio) * (o_oio + o_ooo) * (o_oio + o_oii) / n_xxx
    e_ooo = (o_ooo + o_ioo) * (o_ooo + o_oio) * (o_ooo + o_ooi) / n_xxx
    return e_iii, e_iio, e_ioi, e_oii, e_ioo, e_ooi, e_oio, e_ooo


def observed4(marginals):
    (n_iiii, n_xiii, n_ixii, n_iixi, n_iiix, n_xxii, n_ixxi, n_iixx, n_xixi,
        n_xiix, n_ixix, n_xxxi, n_xxix, n_xixx, n_ixxx, n_xxxx) = marginals
    o_iiii = n_iiii
    o_oiii = n_xiii - n_iiii
    o_ioii = n_ixii - n_iiii
    o_iioi = n_iixi - n_iiii
    o_iiio = n_iiix - n_iiii
    o_ooii = n_xxii - n_iiii - o_oiii - o_ioii
    o_iooi = n_ixxi - n_iiii - o_ioii - o_iioi
    o_iioo = n_iixx - n_iiii - o_iioi - o_iiio
    o_oioi = n_xixi - n_iiii - o_oiii - o_iioi
    o_ioio = n_ixix - n_iiii - o_ioii - o_iiio
    o_oiio = n_ixxi - n_iiii - o_ioii - o_iioi
    o_oooi = (n_xxxi - n_iiii - o_oiii - o_ioii - o_iioi - o_ooii - o_oioi -
        o_iooi)
    o_ooio = (n_xxix - n_iiii - o_oiii - o_ioii - o_iiio - o_ooii - o_oiio -
        o_ioio)
    o_oioo = (n_xixx - n_iiii - o_oiii - o_iioi - o_iiio - o_oioi - o_iioo -
        o_oiio)
    o_iooo = (n_ixxx - n_iiii - o_ioii - o_iioi - o_iiio - o_iooi - o_iioo -
        o_ioio)
    o_oooo = (n_xxxx - n_iiii - o_oiii - o_ioii - o_iioi - o_iiio - o_ooii -
        o_iooi - o_iioo - o_oioi - o_ioio - o_oiio - o_oooi - o_ooio -
        o_oioo - o_iooo)
    return (o_iiii, o_oiii, o_ioii, o_iioi, o_iiio, o_ooii, o_iooi, o_iioo,
        o_oioi, o_ioio, o_oiio, o_oooi, o_ooio, o_oioo, o_iooo, o_oooo)


<mask token>


def create_ngram_star(lemmas):
    from itertools import product
    ngrams = []
    for logical_vector in product((True, False), repeat=ngram_length):
        logical_ngram = ['*' for e in range(ngram_length)]
        for index, logical_value in enumerate(logical_vector):
            if logical_value:
                logical_ngram[index] = lemmas[index]
        ngrams.append(tuple(logical_ngram))
    return ngrams


<mask token>


def calculate_tfidf(ngram_frequency_distr):
    result = []
    ngram_probability = relativize_distr(ngram_frequency_distr)
    for ngram, tf in ngram_probability.iteritems():
        if ngram_frequency_distr[ngram] >= min_frequency:
            idf_avg = 0.0
            result.append((tf * avg_idf(ngram), ngram))
    return sorted(result, reverse=True)


def relativize_distr(distr):
    copy_distr = {}
    all = float(sum(distr.values()))
    for key, value in distr.iteritems():
        copy_distr[key] = distr[key] / all
    return copy_distr


<mask token>


def parse_arguments():
    key = None
    for argument in sys.argv[1:]:
        if argument.startswith('-'):
            key = argument[1:]
            if key == 'h':
                print_help()
            if key not in definable_properties:
                sys.stderr.write('Warning: argument identifier ' + argument +
                    ' unknown\n')
            else:
                properties[key] = []
        elif key is None:
            sys.stderr.write('Warning: argument ' + argument +
                ' without argument identifier' + '\n')
        elif key in definable_properties:
            properties[key].append(argument)
        else:
            sys.stderr.write('Error: unknown argument identifier ' + key + '\n'
                )
            print_help()


<mask token>


def check_properties():
    global term_number
    term_number = None
    global threshold
    threshold = None
    global ranking_method
    global ngram_length
    global output_file
    global position
    global min_frequency
    global seq
    seq = 0
    global norm
    norm = 0
    global terms
    terms = 0
    if 'prop' in properties:
        if properties['prop'] == []:
            sys.stderr.write(
                'Error: no argument given for property file (-prop)\n')
            print_help()
        import re
        line_re = re.compile('(.+?)=(.+)')
        try:
            properties_file = open(properties['prop'][-1])
        except:
            sys.stderr.write('Error: can not open property file (-prop): ' +
                properties['prop'][-1] + '\n')
            print_help()
        i = 0
        for line in properties_file:
            i += 1
            if line.strip().startswith('#'):
                continue
            result = line_re.search(line)
            if result is None:
                sys.stderr.write('Error in property file line ' + str(i) +
                    '\n' + repr(line) + '\n')
                print_help()
            key = result.group(1).strip()
            if '"' in line:
                values = re.findall('"(.+?)"', result.group(2).strip())
            else:
                values = re.split('\\s+', result.group(2).strip())
            if key not in definable_properties:
                sys.stderr.write('Error: unknown argument identifier ' +
                    key + """ (property file)
""")
                print_help()
            properties[key] = values
    missing_properties = mandatory_properties.difference(mandatory_properties
        .intersection(properties))
    if len(missing_properties) > 0:
        sys.stderr.write('Error: these mandatory properties are missing: ' +
            ', '.join(missing_properties) + '\n')
        print_help()
    if 'n' in properties:
        if properties['n'] == []:
            sys.stderr.write(
                'Error: no argument given for number of terms (-n)\n')
            print_help()
        try:
            term_number = int(properties['n'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument for number of terms (-n): ' +
                properties['n'][-1] + '\n')
            print_help()
    if 't' in properties:
        if properties['t'] == []:
            sys.stderr.write('Error: no argument given for threshold (-t)\n')
            print_help()
        try:
            threshold = float(properties['t'][-1])
        except:
            sys.stderr.write('Error: wrong argument for threshold (-t): ' +
                properties['t'][-1] + '\n')
            print_help()
    if properties['m'] == []:
        sys.stderr.write(
            'Error: no argument given for n-gram ranking method (-m)\n')
        print_help()
    ranking_method = properties['m'][-1]
    if ranking_method not in ranking_methods:
        sys.stderr.write(
            'Error: wrong argument for n-gram ranking method (-m): ' +
            ranking_method + '\n')
        print_help()
    if properties['l'] == []:
        sys.stderr.write(
            'Error: no argument given for length of n-grams (-l)\n')
        print_help()
    try:
        ngram_length = int(properties['l'][-1])
        if ngram_length < 1 or ngram_length > 4:
            raise Exception
    except:
        sys.stderr.write(
            'Error: wrong argument for length of n-grams (-l): ' +
            properties['l'][-1] + '\n')
        print_help()
    if ngram_length == 1 and 'idf' not in properties:
        sys.stderr.write(
            'Error: idf file has to be defined for length of n-grams 1 (-l 1)\n'
            )
        print_help()
    if 'o' in properties:
        if properties['o'] == []:
            sys.stderr.write('Error: no argument given output file (-o)\n')
            print_help()
        try:
            output_file = open(properties['o'][-1], 'w')
        except:
            sys.stderr.write('Error: can not write to output file ' +
                properties['o'][-1] + '\n')
            print_help()
    else:
        output_file = sys.stdout
    if 'pos' in properties:
        if len(properties['pos']) < 3:
            sys.stderr.write(
                'Error: wrong number of arguments given for position (-pos)\n')
            print_help()
        try:
            position = [int(e) for e in properties['pos'][-3:]]
            if len(set(position)) != 3:
                raise Exception
        except:
            sys.stderr.write(
                'Error: wrong arguments given for position (-pos): ' + ', '
                .join(properties['pos'][-3:]) + '\n')
            print_help()
    else:
        position = range(3)
    if 'min' in properties:
        if properties['min'] == []:
            sys.stderr.write(
                'Error: no argument given for minimum frequency (-min)\n')
            print_help()
        try:
            min_frequency = int(properties['min'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument given for minimum frequency (-min): ' +
                properties['min'][-1] + '\n')
            print_help()
    if 'idf' in properties:
        if properties['idf'] == []:
            sys.stderr.write('Error: no argument given for idf file (-idf)\n')
            print_help()
    if 'seq' in properties:
        if properties['seq'] == []:
            sys.stderr.write(
                'Error: no argument given for sequence output (-seq)\n')
            print_help()
        if properties['seq'][-1] != '0' and properties['seq'][-1
            ] != '1' and properties['seq'][-1] != '2':
            sys.stderr.write(
                'Error: wrong argument given for sequence output (-seq): ' +
                properties['seq'][-1] + '\n')
            print_help()
        seq = int(properties['seq'][-1])
    if 'norm' in properties:
        if properties['norm'] == []:
            sys.stderr.write(
                'Error: no argument given for normalization (-norm)\n')
            print_help()
        try:
            norm = float(properties['norm'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument given for normalization (-norm): ' +
                properties['norm'][-1] + '\n')
            print_help()
    if 'terms' in properties:
        if properties['terms'] == []:
            sys.stderr.write(
                'Error: no argument given for term output (-terms)\n')
            print_help()
        if properties['terms'][-1] != '0' and properties['terms'][-1] != '1':
            sys.stderr.write(
                'Error: wrong argument given for term output (-terms): ' +
                properties['terms'][-1] + '\n')
            print_help()
        terms = int(properties['terms'][-1])


<mask token>


def read_idf_file():
    if 'idf' not in properties:
        return
    global idf
    idf = {}
    if properties['idf'] == []:
        sys.stderr.write('Error: no argument given for idf file (-idf)\n')
        print_help()
    try:
        idf = dict([(a, float(b)) for a, b in [e.split('\t') for e in
            codecs.open(properties['idf'][-1], 'r', 'utf-8')]])
    except:
        sys.stderr.write('Error: can not read idf file ' + properties['idf'
            ][-1] + '\n')
        print_help()


<mask token>


def check_ngram_for_stops(token_ngram):
    if stop_phrase == []:
        return True
    for token, stop in zip(token_ngram, stop_phrase):
        if stop == 'STOP' and token not in stopwords:
            return False
        elif stop == '!STOP' and token in stopwords:
            return False
    return True


def normalize_result():
    global results
    global norm
    if norm == 0:
        norm = 1
    values = [a for a, b in results]
    if len(values) == 0:
        return
    min_value = min(values)
    max_value = max(values)
    range = float(max_value - min_value)
    for index, (value, ngram) in enumerate(results):
        try:
            results[index] = norm * (value - min_value) / range, ngram
        except ZeroDivisionError:
            results[index] = norm, ngram


def linearly_combine_with_idf():
    normalize_result()
    global results
    results = sorted([(value * 0.5 + avg_idf(ngram) * 0.5, ngram) for value,
        ngram in results], reverse=True)


def output_result():
    i = 0
    for value, ngram in results:
        if threshold is not None:
            if value < threshold:
                break
        if seq == 0:
            output = ' '.join(ngram).encode('utf-8') + '\t(' + '|'.join([e[
                0] for e in sorted(lemma_phrase_map[ngram].items(), key=lambda
                x: -x[1])]) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        elif seq == 1:
            output = ' '.join(sorted(lemma_token_frequency_distr[ngram].
                items(), key=lambda x: x[1])[-1][0]).encode('utf-8'
                ) + '\t(' + '|'.join([e[0] for e in sorted(lemma_phrase_map
                [ngram].items(), key=lambda x: -x[1])]) + ', ' + str(
                ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        elif seq == 2:
            output = ' '.join(ngram).encode('utf-8') + '\t' + ' '.join(sorted
                (lemma_token_frequency_distr[ngram].items(), key=lambda x:
                x[1])[-1][0]).encode('utf-8') + '\t(' + '|'.join([e[0] for
                e in sorted(lemma_phrase_map[ngram].items(), key=lambda x: 
                -x[1])]) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        else:
            for token_sequence, frequency in lemma_token_frequency_distr[ngram
                ].iteritems():
                output = ' '.join(token_sequence).encode('utf-8'
                    ) + '\t(' + '|'.join([e[0] for e in sorted(
                    lemma_phrase_map[ngram].items(), key=lambda x: -x[1])]
                    ) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
                if terms == 0:
                    output += '\t' + str(frequency) + '\t' + str(round(
                        value, 5))
                output_file.write(output + '\n')
        i += 1
        if term_number is not None:
            if i >= term_number:
                break


<mask token>

<mask token>


def calculate_g0_mi(ngram_frequency_distr, unigram_frequency_distr):
    result = []
    ngram_probability = relativize_distr(ngram_frequency_distr)
    unigram_probability = relativize_distr(unigram_frequency_distr)
    from math import log
    for ngram in ngram_probability:
        if ngram_frequency_distr[ngram] >= min_frequency:
            result.append((log(ngram_probability[ngram] / product([
                unigram_probability[e] for e in ngram])), ngram))
    return sorted(result, reverse=True)


def calculate_g0_ll(ngram_frequency):
    result = []
    from math import log
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            ll = 0.0
            for o, e in zip(observed, expected):
                try:
                    ll += o * log(o / e)
                except:
                    pass
            result.append((2 * ll, ngram))
    return sorted(result, reverse=True)


def calculate_g0_chisq(ngram_frequency):
    result = []
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            chisq = 0.0
            for o, e in zip(observed, expected):
                try:
                    chisq += (o - e) ** 2 / e
                except:
                    pass
            result.append((chisq, ngram))
    return sorted(result, reverse=True)


def calculate_g0_tscore(ngram_frequency):
    from math import sqrt
    result = []
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            tscore = float(observed[0] - expected[0]) / sqrt(expected[0])
            result.append((tscore, ngram))
    return sorted(result, reverse=True)


def observed2(marginals):
    n_ii, n_ix, n_xi, n_xx = marginals
    n_oi = n_xi - n_ii
    n_io = n_ix - n_ii
    return n_ii, n_io, n_oi, n_xx - n_ii - n_oi - n_io


def expected2(observed):
    n_ii, n_io, n_oi, n_oo = observed
    n_xx = float(n_ii + n_oi + n_io + n_oo)
    e_ii = (n_ii + n_io) * (n_ii + n_oi) / n_xx
    e_io = (n_ii + n_io) * (n_io + n_oo) / n_xx
    e_oi = (n_oi + n_oo) * (n_ii + n_oi) / n_xx
    e_oo = (n_oi + n_oo) * (n_io + n_oo) / n_xx
    return e_ii, e_io, e_oi, e_oo


def expected_nltk(contingency):
    n_xx = sum(contingency)
    for i in range(4):
        yield (contingency[i] + contingency[i ^ 1]) * (contingency[i] +
            contingency[i ^ 2]) / float(n_xx)


def observed3(marginals):
    n_iii, n_iix, n_ixi, n_ixx, n_xii, n_xix, n_xxi, n_xxx = marginals
    n_oii = n_xii - n_iii
    n_ioi = n_ixi - n_iii
    n_iio = n_iix - n_iii
    n_ooi = n_xxi - n_iii - n_oii - n_ioi
    n_oio = n_xix - n_iii - n_oii - n_iio
    n_ioo = n_ixx - n_iii - n_ioi - n_iio
    n_ooo = n_xxx - n_iii - n_oii - n_ioi - n_iio - n_ooi - n_oio - n_ioo
    return n_iii, n_iio, n_ioi, n_oii, n_ioo, n_ooi, n_oio, n_ooo


def expected3(observed):
    o_iii, o_iio, o_ioi, o_oii, o_ioo, o_ooi, o_oio, o_ooo = observed
    n_xxx = float(o_iii + o_iio + o_ioi + o_oii + o_ioo + o_ooi + o_oio + o_ooo
        )
    e_iii = (o_iii + o_oii) * (o_iii + o_ioi) * (o_iii + o_iio) / n_xxx
    e_iio = (o_iio + o_oio) * (o_iio + o_ioi) * (o_iio + o_iii) / n_xxx
    e_ioi = (o_ioi + o_ooi) * (o_ioi + o_iii) * (o_ioi + o_ioo) / n_xxx
    e_oii = (o_oii + o_iii) * (o_oii + o_ooi) * (o_oii + o_oio) / n_xxx
    e_ioo = (o_ioo + o_ooo) * (o_ioo + o_iio) * (o_ioo + o_ioi) / n_xxx
    e_ooi = (o_ooi + o_ioi) * (o_ooi + o_oii) * (o_ooi + o_ooo) / n_xxx
    e_oio = (o_oio + o_iio) * (o_oio + o_ooo) * (o_oio + o_oii) / n_xxx
    e_ooo = (o_ooo + o_ioo) * (o_ooo + o_oio) * (o_ooo + o_ooi) / n_xxx
    return e_iii, e_iio, e_ioi, e_oii, e_ioo, e_ooi, e_oio, e_ooo


def observed4(marginals):
    (n_iiii, n_xiii, n_ixii, n_iixi, n_iiix, n_xxii, n_ixxi, n_iixx, n_xixi,
        n_xiix, n_ixix, n_xxxi, n_xxix, n_xixx, n_ixxx, n_xxxx) = marginals
    o_iiii = n_iiii
    o_oiii = n_xiii - n_iiii
    o_ioii = n_ixii - n_iiii
    o_iioi = n_iixi - n_iiii
    o_iiio = n_iiix - n_iiii
    o_ooii = n_xxii - n_iiii - o_oiii - o_ioii
    o_iooi = n_ixxi - n_iiii - o_ioii - o_iioi
    o_iioo = n_iixx - n_iiii - o_iioi - o_iiio
    o_oioi = n_xixi - n_iiii - o_oiii - o_iioi
    o_ioio = n_ixix - n_iiii - o_ioii - o_iiio
    o_oiio = n_ixxi - n_iiii - o_ioii - o_iioi
    o_oooi = (n_xxxi - n_iiii - o_oiii - o_ioii - o_iioi - o_ooii - o_oioi -
        o_iooi)
    o_ooio = (n_xxix - n_iiii - o_oiii - o_ioii - o_iiio - o_ooii - o_oiio -
        o_ioio)
    o_oioo = (n_xixx - n_iiii - o_oiii - o_iioi - o_iiio - o_oioi - o_iioo -
        o_oiio)
    o_iooo = (n_ixxx - n_iiii - o_ioii - o_iioi - o_iiio - o_iooi - o_iioo -
        o_ioio)
    o_oooo = (n_xxxx - n_iiii - o_oiii - o_ioii - o_iioi - o_iiio - o_ooii -
        o_iooi - o_iioo - o_oioi - o_ioio - o_oiio - o_oooi - o_ooio -
        o_oioo - o_iooo)
    return (o_iiii, o_oiii, o_ioii, o_iioi, o_iiio, o_ooii, o_iooi, o_iioo,
        o_oioi, o_ioio, o_oiio, o_oooi, o_ooio, o_oioo, o_iooo, o_oooo)


<mask token>


def create_ngram_star(lemmas):
    from itertools import product
    ngrams = []
    for logical_vector in product((True, False), repeat=ngram_length):
        logical_ngram = ['*' for e in range(ngram_length)]
        for index, logical_value in enumerate(logical_vector):
            if logical_value:
                logical_ngram[index] = lemmas[index]
        ngrams.append(tuple(logical_ngram))
    return ngrams


<mask token>


def calculate_tfidf(ngram_frequency_distr):
    result = []
    ngram_probability = relativize_distr(ngram_frequency_distr)
    for ngram, tf in ngram_probability.iteritems():
        if ngram_frequency_distr[ngram] >= min_frequency:
            idf_avg = 0.0
            result.append((tf * avg_idf(ngram), ngram))
    return sorted(result, reverse=True)


def relativize_distr(distr):
    copy_distr = {}
    all = float(sum(distr.values()))
    for key, value in distr.iteritems():
        copy_distr[key] = distr[key] / all
    return copy_distr


<mask token>


def parse_arguments():
    key = None
    for argument in sys.argv[1:]:
        if argument.startswith('-'):
            key = argument[1:]
            if key == 'h':
                print_help()
            if key not in definable_properties:
                sys.stderr.write('Warning: argument identifier ' + argument +
                    ' unknown\n')
            else:
                properties[key] = []
        elif key is None:
            sys.stderr.write('Warning: argument ' + argument +
                ' without argument identifier' + '\n')
        elif key in definable_properties:
            properties[key].append(argument)
        else:
            sys.stderr.write('Error: unknown argument identifier ' + key + '\n'
                )
            print_help()


<mask token>


def check_properties():
    global term_number
    term_number = None
    global threshold
    threshold = None
    global ranking_method
    global ngram_length
    global output_file
    global position
    global min_frequency
    global seq
    seq = 0
    global norm
    norm = 0
    global terms
    terms = 0
    if 'prop' in properties:
        if properties['prop'] == []:
            sys.stderr.write(
                'Error: no argument given for property file (-prop)\n')
            print_help()
        import re
        line_re = re.compile('(.+?)=(.+)')
        try:
            properties_file = open(properties['prop'][-1])
        except:
            sys.stderr.write('Error: can not open property file (-prop): ' +
                properties['prop'][-1] + '\n')
            print_help()
        i = 0
        for line in properties_file:
            i += 1
            if line.strip().startswith('#'):
                continue
            result = line_re.search(line)
            if result is None:
                sys.stderr.write('Error in property file line ' + str(i) +
                    '\n' + repr(line) + '\n')
                print_help()
            key = result.group(1).strip()
            if '"' in line:
                values = re.findall('"(.+?)"', result.group(2).strip())
            else:
                values = re.split('\\s+', result.group(2).strip())
            if key not in definable_properties:
                sys.stderr.write('Error: unknown argument identifier ' +
                    key + """ (property file)
""")
                print_help()
            properties[key] = values
    missing_properties = mandatory_properties.difference(mandatory_properties
        .intersection(properties))
    if len(missing_properties) > 0:
        sys.stderr.write('Error: these mandatory properties are missing: ' +
            ', '.join(missing_properties) + '\n')
        print_help()
    if 'n' in properties:
        if properties['n'] == []:
            sys.stderr.write(
                'Error: no argument given for number of terms (-n)\n')
            print_help()
        try:
            term_number = int(properties['n'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument for number of terms (-n): ' +
                properties['n'][-1] + '\n')
            print_help()
    if 't' in properties:
        if properties['t'] == []:
            sys.stderr.write('Error: no argument given for threshold (-t)\n')
            print_help()
        try:
            threshold = float(properties['t'][-1])
        except:
            sys.stderr.write('Error: wrong argument for threshold (-t): ' +
                properties['t'][-1] + '\n')
            print_help()
    if properties['m'] == []:
        sys.stderr.write(
            'Error: no argument given for n-gram ranking method (-m)\n')
        print_help()
    ranking_method = properties['m'][-1]
    if ranking_method not in ranking_methods:
        sys.stderr.write(
            'Error: wrong argument for n-gram ranking method (-m): ' +
            ranking_method + '\n')
        print_help()
    if properties['l'] == []:
        sys.stderr.write(
            'Error: no argument given for length of n-grams (-l)\n')
        print_help()
    try:
        ngram_length = int(properties['l'][-1])
        if ngram_length < 1 or ngram_length > 4:
            raise Exception
    except:
        sys.stderr.write(
            'Error: wrong argument for length of n-grams (-l): ' +
            properties['l'][-1] + '\n')
        print_help()
    if ngram_length == 1 and 'idf' not in properties:
        sys.stderr.write(
            'Error: idf file has to be defined for length of n-grams 1 (-l 1)\n'
            )
        print_help()
    if 'o' in properties:
        if properties['o'] == []:
            sys.stderr.write('Error: no argument given output file (-o)\n')
            print_help()
        try:
            output_file = open(properties['o'][-1], 'w')
        except:
            sys.stderr.write('Error: can not write to output file ' +
                properties['o'][-1] + '\n')
            print_help()
    else:
        output_file = sys.stdout
    if 'pos' in properties:
        if len(properties['pos']) < 3:
            sys.stderr.write(
                'Error: wrong number of arguments given for position (-pos)\n')
            print_help()
        try:
            position = [int(e) for e in properties['pos'][-3:]]
            if len(set(position)) != 3:
                raise Exception
        except:
            sys.stderr.write(
                'Error: wrong arguments given for position (-pos): ' + ', '
                .join(properties['pos'][-3:]) + '\n')
            print_help()
    else:
        position = range(3)
    if 'min' in properties:
        if properties['min'] == []:
            sys.stderr.write(
                'Error: no argument given for minimum frequency (-min)\n')
            print_help()
        try:
            min_frequency = int(properties['min'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument given for minimum frequency (-min): ' +
                properties['min'][-1] + '\n')
            print_help()
    if 'idf' in properties:
        if properties['idf'] == []:
            sys.stderr.write('Error: no argument given for idf file (-idf)\n')
            print_help()
    if 'seq' in properties:
        if properties['seq'] == []:
            sys.stderr.write(
                'Error: no argument given for sequence output (-seq)\n')
            print_help()
        if properties['seq'][-1] != '0' and properties['seq'][-1
            ] != '1' and properties['seq'][-1] != '2':
            sys.stderr.write(
                'Error: wrong argument given for sequence output (-seq): ' +
                properties['seq'][-1] + '\n')
            print_help()
        seq = int(properties['seq'][-1])
    if 'norm' in properties:
        if properties['norm'] == []:
            sys.stderr.write(
                'Error: no argument given for normalization (-norm)\n')
            print_help()
        try:
            norm = float(properties['norm'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument given for normalization (-norm): ' +
                properties['norm'][-1] + '\n')
            print_help()
    if 'terms' in properties:
        if properties['terms'] == []:
            sys.stderr.write(
                'Error: no argument given for term output (-terms)\n')
            print_help()
        if properties['terms'][-1] != '0' and properties['terms'][-1] != '1':
            sys.stderr.write(
                'Error: wrong argument given for term output (-terms): ' +
                properties['terms'][-1] + '\n')
            print_help()
        terms = int(properties['terms'][-1])


def read_phrase_configuration_file():
    global valid_phrases
    valid_phrases = []
    global stop_phrase
    stop_phrase = []
    global ngram_length
    if properties['p'] == []:
        sys.stderr.write(
            'Error: no argument given for phrase configuration file (-p)\n')
        print_help()
    try:
        phrase_configuration_file = open(properties['p'][-1], 'r')
    except:
        sys.stderr.write('Error: can not read phrase configuration file ' +
            properties['p'][-1] + '\n')
        print_help()
    i = 0
    for line in phrase_configuration_file:
        i += 1
        if line.strip().startswith('#'):
            continue
        if line.strip() == '':
            continue
        valid_phrase = line.strip().split('\t')
        try:
            if ngram_length != len(valid_phrase):
                continue
            if 'STOP' in line:
                if stop_phrase != []:
                    raise Exception
                for stop in valid_phrase:
                    if stop not in ('!STOP', 'STOP', '*'):
                        raise Exception
                stop_phrase = valid_phrase
                continue
            valid_phrase = [re.compile(e) for e in valid_phrase]
        except:
            sys.stderr.write('Error in phrase configuration file line ' +
                str(i) + '\n' + repr(line) + '\n')
            print_help()
        valid_phrases.append(valid_phrase)


def read_stopword_file():
    global stopwords
    stopwords = set()
    if 's' not in properties:
        return
    if properties['s'] == []:
        sys.stderr.write('Error: no argument given for stop-word file (-s)\n')
        print_help()
    try:
        stopwords = set([e.strip() for e in codecs.open(properties['s'][-1],
            'r', 'utf-8')])
    except:
        sys.stderr.write('Error: can not read stop-word file ' + properties
            ['s'][-1] + '\n')
        print_help()


def read_idf_file():
    if 'idf' not in properties:
        return
    global idf
    idf = {}
    if properties['idf'] == []:
        sys.stderr.write('Error: no argument given for idf file (-idf)\n')
        print_help()
    try:
        idf = dict([(a, float(b)) for a, b in [e.split('\t') for e in
            codecs.open(properties['idf'][-1], 'r', 'utf-8')]])
    except:
        sys.stderr.write('Error: can not read idf file ' + properties['idf'
            ][-1] + '\n')
        print_help()


def read_input_text():
    enamex = 0
    numex = 0
    timex = 0
    if properties['i'] == []:
        sys.stderr.write('Error: no argument given for input file (-i)\n')
        print_help()
    path = properties['i'][-1]
    try:
        input_file = codecs.open(path, 'r', 'utf-8')
    except:
        sys.stderr.write('Error: can not read input file ' + path + '\n')
        print_help()
    i = 0
    ngram = [None for e in range(ngram_length)]
    global ngram_frequency_distr
    ngram_frequency_distr = {}
    global unigram_frequency_distr
    unigram_frequency_distr = {}
    global lemma_token_frequency_distr
    lemma_token_frequency_distr = {}
    global lemma_phrase_map
    lemma_phrase_map = {}
    for line in input_file:
        if i == 0:
            if line.startswith(u'\ufeff'):
                line = line[1:]
        i += 1
        split_line = line.strip().split('\t')
        if split_line == ['']:
            continue
        if split_line[0][0] == '<':
            if split_line[0].startswith('<NUMEX'):
                numex += 1
            elif split_line[0].startswith('<ENAMEX'):
                enamex += 1
            elif split_line[0].startswith('<TIMEX'):
                timex += 1
            elif split_line[0].startswith('</NUMEX'):
                numex -= 1
            elif split_line[0].startswith('</ENAMEX'):
                enamex -= 1
            elif split_line[0].startswith('</TIMEX'):
                timex -= 1
            else:
                continue
            ngram = [None for e in range(ngram_length)]
            if enamex < 0 or numex < 0 or timex < 0:
                sys.stderr.write(
                    'Error: closing bracket without open on line ' + str(i) +
                    '\n' + repr(line) + '\n')
                sys.exit(1)
            continue
        if enamex != 0 or numex != 0 or timex != 0:
            continue
        try:
            token, pos, lemma = split_line[position[0]], split_line[position[1]
                ], split_line[position[2]]
            token = token.lower()
            lemma = lemma.lower()
        except:
            sys.stderr.write('Error in input file line ' + str(i) + '\n' +
                repr(line) + '\n')
            print_help()
        if ranking_method in ('dice', 'mi'):
            unigram_frequency_distr[lemma] = unigram_frequency_distr.get(lemma,
                0) + 1
        ngram = ngram[1:]
        ngram.append((token, pos, lemma))
        try:
            tokens = tuple([e[0] for e in ngram])
            poses = tuple([e[1] for e in ngram])
            lemmas = tuple([e[2] for e in ngram])
        except:
            continue
        if ranking_method in ('ll', 'chisq', 'tscore'):
            for star_ngram in create_ngram_star(lemmas):
                ngram_frequency_distr[star_ngram] = ngram_frequency_distr.get(
                    star_ngram, 0) + 1
        phrase = check_ngram_for_phrases(poses)
        if phrase != None and check_ngram_for_stops(tokens):
            if lemmas not in lemma_phrase_map:
                lemma_phrase_map[lemmas] = {}
            lemma_phrase_map[lemmas][phrase] = lemma_phrase_map[lemmas].get(
                phrase, 0) + 1
            if ranking_method in ('dice', 'mi', 'tfidf'):
                ngram_frequency_distr[lemmas] = ngram_frequency_distr.get(
                    lemmas, 0) + 1
            if lemmas not in lemma_token_frequency_distr:
                lemma_token_frequency_distr[lemmas] = {}
            lemma_token_frequency_distr[lemmas][tokens
                ] = lemma_token_frequency_distr[lemmas].get(tokens, 0) + 1
    global results
    if ranking_method in ('dice', 'mi'):
        results = ranking_methods[ranking_method](ngram_frequency_distr,
            unigram_frequency_distr)
    elif ranking_method in ('ll', 'chisq', 'tscore', 'tfidf'):
        results = ranking_methods[ranking_method](ngram_frequency_distr)


<mask token>


def check_ngram_for_stops(token_ngram):
    if stop_phrase == []:
        return True
    for token, stop in zip(token_ngram, stop_phrase):
        if stop == 'STOP' and token not in stopwords:
            return False
        elif stop == '!STOP' and token in stopwords:
            return False
    return True


def normalize_result():
    global results
    global norm
    if norm == 0:
        norm = 1
    values = [a for a, b in results]
    if len(values) == 0:
        return
    min_value = min(values)
    max_value = max(values)
    range = float(max_value - min_value)
    for index, (value, ngram) in enumerate(results):
        try:
            results[index] = norm * (value - min_value) / range, ngram
        except ZeroDivisionError:
            results[index] = norm, ngram


def linearly_combine_with_idf():
    normalize_result()
    global results
    results = sorted([(value * 0.5 + avg_idf(ngram) * 0.5, ngram) for value,
        ngram in results], reverse=True)


def output_result():
    i = 0
    for value, ngram in results:
        if threshold is not None:
            if value < threshold:
                break
        if seq == 0:
            output = ' '.join(ngram).encode('utf-8') + '\t(' + '|'.join([e[
                0] for e in sorted(lemma_phrase_map[ngram].items(), key=lambda
                x: -x[1])]) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        elif seq == 1:
            output = ' '.join(sorted(lemma_token_frequency_distr[ngram].
                items(), key=lambda x: x[1])[-1][0]).encode('utf-8'
                ) + '\t(' + '|'.join([e[0] for e in sorted(lemma_phrase_map
                [ngram].items(), key=lambda x: -x[1])]) + ', ' + str(
                ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        elif seq == 2:
            output = ' '.join(ngram).encode('utf-8') + '\t' + ' '.join(sorted
                (lemma_token_frequency_distr[ngram].items(), key=lambda x:
                x[1])[-1][0]).encode('utf-8') + '\t(' + '|'.join([e[0] for
                e in sorted(lemma_phrase_map[ngram].items(), key=lambda x: 
                -x[1])]) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        else:
            for token_sequence, frequency in lemma_token_frequency_distr[ngram
                ].iteritems():
                output = ' '.join(token_sequence).encode('utf-8'
                    ) + '\t(' + '|'.join([e[0] for e in sorted(
                    lemma_phrase_map[ngram].items(), key=lambda x: -x[1])]
                    ) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
                if terms == 0:
                    output += '\t' + str(frequency) + '\t' + str(round(
                        value, 5))
                output_file.write(output + '\n')
        i += 1
        if term_number is not None:
            if i >= term_number:
                break


<mask token>

<mask token>


def calculate_g0_mi(ngram_frequency_distr, unigram_frequency_distr):
    result = []
    ngram_probability = relativize_distr(ngram_frequency_distr)
    unigram_probability = relativize_distr(unigram_frequency_distr)
    from math import log
    for ngram in ngram_probability:
        if ngram_frequency_distr[ngram] >= min_frequency:
            result.append((log(ngram_probability[ngram] / product([
                unigram_probability[e] for e in ngram])), ngram))
    return sorted(result, reverse=True)


def calculate_g0_ll(ngram_frequency):
    result = []
    from math import log
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            ll = 0.0
            for o, e in zip(observed, expected):
                try:
                    ll += o * log(o / e)
                except:
                    pass
            result.append((2 * ll, ngram))
    return sorted(result, reverse=True)


def calculate_g0_chisq(ngram_frequency):
    result = []
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            chisq = 0.0
            for o, e in zip(observed, expected):
                try:
                    chisq += (o - e) ** 2 / e
                except:
                    pass
            result.append((chisq, ngram))
    return sorted(result, reverse=True)


def calculate_g0_tscore(ngram_frequency):
    from math import sqrt
    result = []
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            tscore = float(observed[0] - expected[0]) / sqrt(expected[0])
            result.append((tscore, ngram))
    return sorted(result, reverse=True)


def observed2(marginals):
    n_ii, n_ix, n_xi, n_xx = marginals
    n_oi = n_xi - n_ii
    n_io = n_ix - n_ii
    return n_ii, n_io, n_oi, n_xx - n_ii - n_oi - n_io


def expected2(observed):
    n_ii, n_io, n_oi, n_oo = observed
    n_xx = float(n_ii + n_oi + n_io + n_oo)
    e_ii = (n_ii + n_io) * (n_ii + n_oi) / n_xx
    e_io = (n_ii + n_io) * (n_io + n_oo) / n_xx
    e_oi = (n_oi + n_oo) * (n_ii + n_oi) / n_xx
    e_oo = (n_oi + n_oo) * (n_io + n_oo) / n_xx
    return e_ii, e_io, e_oi, e_oo


def expected_nltk(contingency):
    n_xx = sum(contingency)
    for i in range(4):
        yield (contingency[i] + contingency[i ^ 1]) * (contingency[i] +
            contingency[i ^ 2]) / float(n_xx)


def observed3(marginals):
    n_iii, n_iix, n_ixi, n_ixx, n_xii, n_xix, n_xxi, n_xxx = marginals
    n_oii = n_xii - n_iii
    n_ioi = n_ixi - n_iii
    n_iio = n_iix - n_iii
    n_ooi = n_xxi - n_iii - n_oii - n_ioi
    n_oio = n_xix - n_iii - n_oii - n_iio
    n_ioo = n_ixx - n_iii - n_ioi - n_iio
    n_ooo = n_xxx - n_iii - n_oii - n_ioi - n_iio - n_ooi - n_oio - n_ioo
    return n_iii, n_iio, n_ioi, n_oii, n_ioo, n_ooi, n_oio, n_ooo


def expected3(observed):
    o_iii, o_iio, o_ioi, o_oii, o_ioo, o_ooi, o_oio, o_ooo = observed
    n_xxx = float(o_iii + o_iio + o_ioi + o_oii + o_ioo + o_ooi + o_oio + o_ooo
        )
    e_iii = (o_iii + o_oii) * (o_iii + o_ioi) * (o_iii + o_iio) / n_xxx
    e_iio = (o_iio + o_oio) * (o_iio + o_ioi) * (o_iio + o_iii) / n_xxx
    e_ioi = (o_ioi + o_ooi) * (o_ioi + o_iii) * (o_ioi + o_ioo) / n_xxx
    e_oii = (o_oii + o_iii) * (o_oii + o_ooi) * (o_oii + o_oio) / n_xxx
    e_ioo = (o_ioo + o_ooo) * (o_ioo + o_iio) * (o_ioo + o_ioi) / n_xxx
    e_ooi = (o_ooi + o_ioi) * (o_ooi + o_oii) * (o_ooi + o_ooo) / n_xxx
    e_oio = (o_oio + o_iio) * (o_oio + o_ooo) * (o_oio + o_oii) / n_xxx
    e_ooo = (o_ooo + o_ioo) * (o_ooo + o_oio) * (o_ooo + o_ooi) / n_xxx
    return e_iii, e_iio, e_ioi, e_oii, e_ioo, e_ooi, e_oio, e_ooo


def observed4(marginals):
    (n_iiii, n_xiii, n_ixii, n_iixi, n_iiix, n_xxii, n_ixxi, n_iixx, n_xixi,
        n_xiix, n_ixix, n_xxxi, n_xxix, n_xixx, n_ixxx, n_xxxx) = marginals
    o_iiii = n_iiii
    o_oiii = n_xiii - n_iiii
    o_ioii = n_ixii - n_iiii
    o_iioi = n_iixi - n_iiii
    o_iiio = n_iiix - n_iiii
    o_ooii = n_xxii - n_iiii - o_oiii - o_ioii
    o_iooi = n_ixxi - n_iiii - o_ioii - o_iioi
    o_iioo = n_iixx - n_iiii - o_iioi - o_iiio
    o_oioi = n_xixi - n_iiii - o_oiii - o_iioi
    o_ioio = n_ixix - n_iiii - o_ioii - o_iiio
    o_oiio = n_ixxi - n_iiii - o_ioii - o_iioi
    o_oooi = (n_xxxi - n_iiii - o_oiii - o_ioii - o_iioi - o_ooii - o_oioi -
        o_iooi)
    o_ooio = (n_xxix - n_iiii - o_oiii - o_ioii - o_iiio - o_ooii - o_oiio -
        o_ioio)
    o_oioo = (n_xixx - n_iiii - o_oiii - o_iioi - o_iiio - o_oioi - o_iioo -
        o_oiio)
    o_iooo = (n_ixxx - n_iiii - o_ioii - o_iioi - o_iiio - o_iooi - o_iioo -
        o_ioio)
    o_oooo = (n_xxxx - n_iiii - o_oiii - o_ioii - o_iioi - o_iiio - o_ooii -
        o_iooi - o_iioo - o_oioi - o_ioio - o_oiio - o_oooi - o_ooio -
        o_oioo - o_iooo)
    return (o_iiii, o_oiii, o_ioii, o_iioi, o_iiio, o_ooii, o_iooi, o_iioo,
        o_oioi, o_ioio, o_oiio, o_oooi, o_ooio, o_oioo, o_iooo, o_oooo)


<mask token>


def create_ngram_star(lemmas):
    from itertools import product
    ngrams = []
    for logical_vector in product((True, False), repeat=ngram_length):
        logical_ngram = ['*' for e in range(ngram_length)]
        for index, logical_value in enumerate(logical_vector):
            if logical_value:
                logical_ngram[index] = lemmas[index]
        ngrams.append(tuple(logical_ngram))
    return ngrams


<mask token>


def avg_idf(ngram):
    max_idf = max(idf.values())
    avg_idf = 0.0
    for lemma in ngram:
        avg_idf += idf.get(lemma, max_idf)
    return avg_idf / len(ngram)


def calculate_tfidf(ngram_frequency_distr):
    result = []
    ngram_probability = relativize_distr(ngram_frequency_distr)
    for ngram, tf in ngram_probability.iteritems():
        if ngram_frequency_distr[ngram] >= min_frequency:
            idf_avg = 0.0
            result.append((tf * avg_idf(ngram), ngram))
    return sorted(result, reverse=True)


def relativize_distr(distr):
    copy_distr = {}
    all = float(sum(distr.values()))
    for key, value in distr.iteritems():
        copy_distr[key] = distr[key] / all
    return copy_distr


<mask token>


def parse_arguments():
    key = None
    for argument in sys.argv[1:]:
        if argument.startswith('-'):
            key = argument[1:]
            if key == 'h':
                print_help()
            if key not in definable_properties:
                sys.stderr.write('Warning: argument identifier ' + argument +
                    ' unknown\n')
            else:
                properties[key] = []
        elif key is None:
            sys.stderr.write('Warning: argument ' + argument +
                ' without argument identifier' + '\n')
        elif key in definable_properties:
            properties[key].append(argument)
        else:
            sys.stderr.write('Error: unknown argument identifier ' + key + '\n'
                )
            print_help()


<mask token>


def check_properties():
    global term_number
    term_number = None
    global threshold
    threshold = None
    global ranking_method
    global ngram_length
    global output_file
    global position
    global min_frequency
    global seq
    seq = 0
    global norm
    norm = 0
    global terms
    terms = 0
    if 'prop' in properties:
        if properties['prop'] == []:
            sys.stderr.write(
                'Error: no argument given for property file (-prop)\n')
            print_help()
        import re
        line_re = re.compile('(.+?)=(.+)')
        try:
            properties_file = open(properties['prop'][-1])
        except:
            sys.stderr.write('Error: can not open property file (-prop): ' +
                properties['prop'][-1] + '\n')
            print_help()
        i = 0
        for line in properties_file:
            i += 1
            if line.strip().startswith('#'):
                continue
            result = line_re.search(line)
            if result is None:
                sys.stderr.write('Error in property file line ' + str(i) +
                    '\n' + repr(line) + '\n')
                print_help()
            key = result.group(1).strip()
            if '"' in line:
                values = re.findall('"(.+?)"', result.group(2).strip())
            else:
                values = re.split('\\s+', result.group(2).strip())
            if key not in definable_properties:
                sys.stderr.write('Error: unknown argument identifier ' +
                    key + """ (property file)
""")
                print_help()
            properties[key] = values
    missing_properties = mandatory_properties.difference(mandatory_properties
        .intersection(properties))
    if len(missing_properties) > 0:
        sys.stderr.write('Error: these mandatory properties are missing: ' +
            ', '.join(missing_properties) + '\n')
        print_help()
    if 'n' in properties:
        if properties['n'] == []:
            sys.stderr.write(
                'Error: no argument given for number of terms (-n)\n')
            print_help()
        try:
            term_number = int(properties['n'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument for number of terms (-n): ' +
                properties['n'][-1] + '\n')
            print_help()
    if 't' in properties:
        if properties['t'] == []:
            sys.stderr.write('Error: no argument given for threshold (-t)\n')
            print_help()
        try:
            threshold = float(properties['t'][-1])
        except:
            sys.stderr.write('Error: wrong argument for threshold (-t): ' +
                properties['t'][-1] + '\n')
            print_help()
    if properties['m'] == []:
        sys.stderr.write(
            'Error: no argument given for n-gram ranking method (-m)\n')
        print_help()
    ranking_method = properties['m'][-1]
    if ranking_method not in ranking_methods:
        sys.stderr.write(
            'Error: wrong argument for n-gram ranking method (-m): ' +
            ranking_method + '\n')
        print_help()
    if properties['l'] == []:
        sys.stderr.write(
            'Error: no argument given for length of n-grams (-l)\n')
        print_help()
    try:
        ngram_length = int(properties['l'][-1])
        if ngram_length < 1 or ngram_length > 4:
            raise Exception
    except:
        sys.stderr.write(
            'Error: wrong argument for length of n-grams (-l): ' +
            properties['l'][-1] + '\n')
        print_help()
    if ngram_length == 1 and 'idf' not in properties:
        sys.stderr.write(
            'Error: idf file has to be defined for length of n-grams 1 (-l 1)\n'
            )
        print_help()
    if 'o' in properties:
        if properties['o'] == []:
            sys.stderr.write('Error: no argument given output file (-o)\n')
            print_help()
        try:
            output_file = open(properties['o'][-1], 'w')
        except:
            sys.stderr.write('Error: can not write to output file ' +
                properties['o'][-1] + '\n')
            print_help()
    else:
        output_file = sys.stdout
    if 'pos' in properties:
        if len(properties['pos']) < 3:
            sys.stderr.write(
                'Error: wrong number of arguments given for position (-pos)\n')
            print_help()
        try:
            position = [int(e) for e in properties['pos'][-3:]]
            if len(set(position)) != 3:
                raise Exception
        except:
            sys.stderr.write(
                'Error: wrong arguments given for position (-pos): ' + ', '
                .join(properties['pos'][-3:]) + '\n')
            print_help()
    else:
        position = range(3)
    if 'min' in properties:
        if properties['min'] == []:
            sys.stderr.write(
                'Error: no argument given for minimum frequency (-min)\n')
            print_help()
        try:
            min_frequency = int(properties['min'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument given for minimum frequency (-min): ' +
                properties['min'][-1] + '\n')
            print_help()
    if 'idf' in properties:
        if properties['idf'] == []:
            sys.stderr.write('Error: no argument given for idf file (-idf)\n')
            print_help()
    if 'seq' in properties:
        if properties['seq'] == []:
            sys.stderr.write(
                'Error: no argument given for sequence output (-seq)\n')
            print_help()
        if properties['seq'][-1] != '0' and properties['seq'][-1
            ] != '1' and properties['seq'][-1] != '2':
            sys.stderr.write(
                'Error: wrong argument given for sequence output (-seq): ' +
                properties['seq'][-1] + '\n')
            print_help()
        seq = int(properties['seq'][-1])
    if 'norm' in properties:
        if properties['norm'] == []:
            sys.stderr.write(
                'Error: no argument given for normalization (-norm)\n')
            print_help()
        try:
            norm = float(properties['norm'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument given for normalization (-norm): ' +
                properties['norm'][-1] + '\n')
            print_help()
    if 'terms' in properties:
        if properties['terms'] == []:
            sys.stderr.write(
                'Error: no argument given for term output (-terms)\n')
            print_help()
        if properties['terms'][-1] != '0' and properties['terms'][-1] != '1':
            sys.stderr.write(
                'Error: wrong argument given for term output (-terms): ' +
                properties['terms'][-1] + '\n')
            print_help()
        terms = int(properties['terms'][-1])


def read_phrase_configuration_file():
    global valid_phrases
    valid_phrases = []
    global stop_phrase
    stop_phrase = []
    global ngram_length
    if properties['p'] == []:
        sys.stderr.write(
            'Error: no argument given for phrase configuration file (-p)\n')
        print_help()
    try:
        phrase_configuration_file = open(properties['p'][-1], 'r')
    except:
        sys.stderr.write('Error: can not read phrase configuration file ' +
            properties['p'][-1] + '\n')
        print_help()
    i = 0
    for line in phrase_configuration_file:
        i += 1
        if line.strip().startswith('#'):
            continue
        if line.strip() == '':
            continue
        valid_phrase = line.strip().split('\t')
        try:
            if ngram_length != len(valid_phrase):
                continue
            if 'STOP' in line:
                if stop_phrase != []:
                    raise Exception
                for stop in valid_phrase:
                    if stop not in ('!STOP', 'STOP', '*'):
                        raise Exception
                stop_phrase = valid_phrase
                continue
            valid_phrase = [re.compile(e) for e in valid_phrase]
        except:
            sys.stderr.write('Error in phrase configuration file line ' +
                str(i) + '\n' + repr(line) + '\n')
            print_help()
        valid_phrases.append(valid_phrase)


def read_stopword_file():
    global stopwords
    stopwords = set()
    if 's' not in properties:
        return
    if properties['s'] == []:
        sys.stderr.write('Error: no argument given for stop-word file (-s)\n')
        print_help()
    try:
        stopwords = set([e.strip() for e in codecs.open(properties['s'][-1],
            'r', 'utf-8')])
    except:
        sys.stderr.write('Error: can not read stop-word file ' + properties
            ['s'][-1] + '\n')
        print_help()


def read_idf_file():
    if 'idf' not in properties:
        return
    global idf
    idf = {}
    if properties['idf'] == []:
        sys.stderr.write('Error: no argument given for idf file (-idf)\n')
        print_help()
    try:
        idf = dict([(a, float(b)) for a, b in [e.split('\t') for e in
            codecs.open(properties['idf'][-1], 'r', 'utf-8')]])
    except:
        sys.stderr.write('Error: can not read idf file ' + properties['idf'
            ][-1] + '\n')
        print_help()


def read_input_text():
    enamex = 0
    numex = 0
    timex = 0
    if properties['i'] == []:
        sys.stderr.write('Error: no argument given for input file (-i)\n')
        print_help()
    path = properties['i'][-1]
    try:
        input_file = codecs.open(path, 'r', 'utf-8')
    except:
        sys.stderr.write('Error: can not read input file ' + path + '\n')
        print_help()
    i = 0
    ngram = [None for e in range(ngram_length)]
    global ngram_frequency_distr
    ngram_frequency_distr = {}
    global unigram_frequency_distr
    unigram_frequency_distr = {}
    global lemma_token_frequency_distr
    lemma_token_frequency_distr = {}
    global lemma_phrase_map
    lemma_phrase_map = {}
    for line in input_file:
        if i == 0:
            if line.startswith(u'\ufeff'):
                line = line[1:]
        i += 1
        split_line = line.strip().split('\t')
        if split_line == ['']:
            continue
        if split_line[0][0] == '<':
            if split_line[0].startswith('<NUMEX'):
                numex += 1
            elif split_line[0].startswith('<ENAMEX'):
                enamex += 1
            elif split_line[0].startswith('<TIMEX'):
                timex += 1
            elif split_line[0].startswith('</NUMEX'):
                numex -= 1
            elif split_line[0].startswith('</ENAMEX'):
                enamex -= 1
            elif split_line[0].startswith('</TIMEX'):
                timex -= 1
            else:
                continue
            ngram = [None for e in range(ngram_length)]
            if enamex < 0 or numex < 0 or timex < 0:
                sys.stderr.write(
                    'Error: closing bracket without open on line ' + str(i) +
                    '\n' + repr(line) + '\n')
                sys.exit(1)
            continue
        if enamex != 0 or numex != 0 or timex != 0:
            continue
        try:
            token, pos, lemma = split_line[position[0]], split_line[position[1]
                ], split_line[position[2]]
            token = token.lower()
            lemma = lemma.lower()
        except:
            sys.stderr.write('Error in input file line ' + str(i) + '\n' +
                repr(line) + '\n')
            print_help()
        if ranking_method in ('dice', 'mi'):
            unigram_frequency_distr[lemma] = unigram_frequency_distr.get(lemma,
                0) + 1
        ngram = ngram[1:]
        ngram.append((token, pos, lemma))
        try:
            tokens = tuple([e[0] for e in ngram])
            poses = tuple([e[1] for e in ngram])
            lemmas = tuple([e[2] for e in ngram])
        except:
            continue
        if ranking_method in ('ll', 'chisq', 'tscore'):
            for star_ngram in create_ngram_star(lemmas):
                ngram_frequency_distr[star_ngram] = ngram_frequency_distr.get(
                    star_ngram, 0) + 1
        phrase = check_ngram_for_phrases(poses)
        if phrase != None and check_ngram_for_stops(tokens):
            if lemmas not in lemma_phrase_map:
                lemma_phrase_map[lemmas] = {}
            lemma_phrase_map[lemmas][phrase] = lemma_phrase_map[lemmas].get(
                phrase, 0) + 1
            if ranking_method in ('dice', 'mi', 'tfidf'):
                ngram_frequency_distr[lemmas] = ngram_frequency_distr.get(
                    lemmas, 0) + 1
            if lemmas not in lemma_token_frequency_distr:
                lemma_token_frequency_distr[lemmas] = {}
            lemma_token_frequency_distr[lemmas][tokens
                ] = lemma_token_frequency_distr[lemmas].get(tokens, 0) + 1
    global results
    if ranking_method in ('dice', 'mi'):
        results = ranking_methods[ranking_method](ngram_frequency_distr,
            unigram_frequency_distr)
    elif ranking_method in ('ll', 'chisq', 'tscore', 'tfidf'):
        results = ranking_methods[ranking_method](ngram_frequency_distr)


def check_ngram_for_phrases(pos_ngram):
    for phrase in valid_phrases:
        valid = True
        for pos, regex in zip(pos_ngram, phrase):
            if pos is None:
                valid = False
                break
            if regex.match(pos) is None:
                valid = False
                break
        if valid:
            return ' '.join([e.pattern for e in phrase])


def check_ngram_for_stops(token_ngram):
    if stop_phrase == []:
        return True
    for token, stop in zip(token_ngram, stop_phrase):
        if stop == 'STOP' and token not in stopwords:
            return False
        elif stop == '!STOP' and token in stopwords:
            return False
    return True


def normalize_result():
    global results
    global norm
    if norm == 0:
        norm = 1
    values = [a for a, b in results]
    if len(values) == 0:
        return
    min_value = min(values)
    max_value = max(values)
    range = float(max_value - min_value)
    for index, (value, ngram) in enumerate(results):
        try:
            results[index] = norm * (value - min_value) / range, ngram
        except ZeroDivisionError:
            results[index] = norm, ngram


def linearly_combine_with_idf():
    normalize_result()
    global results
    results = sorted([(value * 0.5 + avg_idf(ngram) * 0.5, ngram) for value,
        ngram in results], reverse=True)


def output_result():
    i = 0
    for value, ngram in results:
        if threshold is not None:
            if value < threshold:
                break
        if seq == 0:
            output = ' '.join(ngram).encode('utf-8') + '\t(' + '|'.join([e[
                0] for e in sorted(lemma_phrase_map[ngram].items(), key=lambda
                x: -x[1])]) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        elif seq == 1:
            output = ' '.join(sorted(lemma_token_frequency_distr[ngram].
                items(), key=lambda x: x[1])[-1][0]).encode('utf-8'
                ) + '\t(' + '|'.join([e[0] for e in sorted(lemma_phrase_map
                [ngram].items(), key=lambda x: -x[1])]) + ', ' + str(
                ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        elif seq == 2:
            output = ' '.join(ngram).encode('utf-8') + '\t' + ' '.join(sorted
                (lemma_token_frequency_distr[ngram].items(), key=lambda x:
                x[1])[-1][0]).encode('utf-8') + '\t(' + '|'.join([e[0] for
                e in sorted(lemma_phrase_map[ngram].items(), key=lambda x: 
                -x[1])]) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        else:
            for token_sequence, frequency in lemma_token_frequency_distr[ngram
                ].iteritems():
                output = ' '.join(token_sequence).encode('utf-8'
                    ) + '\t(' + '|'.join([e[0] for e in sorted(
                    lemma_phrase_map[ngram].items(), key=lambda x: -x[1])]
                    ) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
                if terms == 0:
                    output += '\t' + str(frequency) + '\t' + str(round(
                        value, 5))
                output_file.write(output + '\n')
        i += 1
        if term_number is not None:
            if i >= term_number:
                break


<mask token>

<mask token>


def calculate_g0_mi(ngram_frequency_distr, unigram_frequency_distr):
    result = []
    ngram_probability = relativize_distr(ngram_frequency_distr)
    unigram_probability = relativize_distr(unigram_frequency_distr)
    from math import log
    for ngram in ngram_probability:
        if ngram_frequency_distr[ngram] >= min_frequency:
            result.append((log(ngram_probability[ngram] / product([
                unigram_probability[e] for e in ngram])), ngram))
    return sorted(result, reverse=True)


def calculate_g0_ll(ngram_frequency):
    result = []
    from math import log
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            ll = 0.0
            for o, e in zip(observed, expected):
                try:
                    ll += o * log(o / e)
                except:
                    pass
            result.append((2 * ll, ngram))
    return sorted(result, reverse=True)


def calculate_g0_chisq(ngram_frequency):
    result = []
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            chisq = 0.0
            for o, e in zip(observed, expected):
                try:
                    chisq += (o - e) ** 2 / e
                except:
                    pass
            result.append((chisq, ngram))
    return sorted(result, reverse=True)


def calculate_g0_tscore(ngram_frequency):
    from math import sqrt
    result = []
    observed_functions = [observed2, observed3, observed4]
    expected_functions = [expected2, expected3, expected4]
    for ngram in lemma_token_frequency_distr:
        if ngram_frequency[ngram] >= min_frequency:
            marginals = [ngram_frequency[e] for e in create_ngram_star(ngram)]
            observed = observed_functions[ngram_length - 2](marginals)
            expected = expected_functions[ngram_length - 2](observed)
            tscore = float(observed[0] - expected[0]) / sqrt(expected[0])
            result.append((tscore, ngram))
    return sorted(result, reverse=True)


def observed2(marginals):
    n_ii, n_ix, n_xi, n_xx = marginals
    n_oi = n_xi - n_ii
    n_io = n_ix - n_ii
    return n_ii, n_io, n_oi, n_xx - n_ii - n_oi - n_io


def expected2(observed):
    n_ii, n_io, n_oi, n_oo = observed
    n_xx = float(n_ii + n_oi + n_io + n_oo)
    e_ii = (n_ii + n_io) * (n_ii + n_oi) / n_xx
    e_io = (n_ii + n_io) * (n_io + n_oo) / n_xx
    e_oi = (n_oi + n_oo) * (n_ii + n_oi) / n_xx
    e_oo = (n_oi + n_oo) * (n_io + n_oo) / n_xx
    return e_ii, e_io, e_oi, e_oo


def expected_nltk(contingency):
    n_xx = sum(contingency)
    for i in range(4):
        yield (contingency[i] + contingency[i ^ 1]) * (contingency[i] +
            contingency[i ^ 2]) / float(n_xx)


def observed3(marginals):
    n_iii, n_iix, n_ixi, n_ixx, n_xii, n_xix, n_xxi, n_xxx = marginals
    n_oii = n_xii - n_iii
    n_ioi = n_ixi - n_iii
    n_iio = n_iix - n_iii
    n_ooi = n_xxi - n_iii - n_oii - n_ioi
    n_oio = n_xix - n_iii - n_oii - n_iio
    n_ioo = n_ixx - n_iii - n_ioi - n_iio
    n_ooo = n_xxx - n_iii - n_oii - n_ioi - n_iio - n_ooi - n_oio - n_ioo
    return n_iii, n_iio, n_ioi, n_oii, n_ioo, n_ooi, n_oio, n_ooo


def expected3(observed):
    o_iii, o_iio, o_ioi, o_oii, o_ioo, o_ooi, o_oio, o_ooo = observed
    n_xxx = float(o_iii + o_iio + o_ioi + o_oii + o_ioo + o_ooi + o_oio + o_ooo
        )
    e_iii = (o_iii + o_oii) * (o_iii + o_ioi) * (o_iii + o_iio) / n_xxx
    e_iio = (o_iio + o_oio) * (o_iio + o_ioi) * (o_iio + o_iii) / n_xxx
    e_ioi = (o_ioi + o_ooi) * (o_ioi + o_iii) * (o_ioi + o_ioo) / n_xxx
    e_oii = (o_oii + o_iii) * (o_oii + o_ooi) * (o_oii + o_oio) / n_xxx
    e_ioo = (o_ioo + o_ooo) * (o_ioo + o_iio) * (o_ioo + o_ioi) / n_xxx
    e_ooi = (o_ooi + o_ioi) * (o_ooi + o_oii) * (o_ooi + o_ooo) / n_xxx
    e_oio = (o_oio + o_iio) * (o_oio + o_ooo) * (o_oio + o_oii) / n_xxx
    e_ooo = (o_ooo + o_ioo) * (o_ooo + o_oio) * (o_ooo + o_ooi) / n_xxx
    return e_iii, e_iio, e_ioi, e_oii, e_ioo, e_ooi, e_oio, e_ooo


def observed4(marginals):
    (n_iiii, n_xiii, n_ixii, n_iixi, n_iiix, n_xxii, n_ixxi, n_iixx, n_xixi,
        n_xiix, n_ixix, n_xxxi, n_xxix, n_xixx, n_ixxx, n_xxxx) = marginals
    o_iiii = n_iiii
    o_oiii = n_xiii - n_iiii
    o_ioii = n_ixii - n_iiii
    o_iioi = n_iixi - n_iiii
    o_iiio = n_iiix - n_iiii
    o_ooii = n_xxii - n_iiii - o_oiii - o_ioii
    o_iooi = n_ixxi - n_iiii - o_ioii - o_iioi
    o_iioo = n_iixx - n_iiii - o_iioi - o_iiio
    o_oioi = n_xixi - n_iiii - o_oiii - o_iioi
    o_ioio = n_ixix - n_iiii - o_ioii - o_iiio
    o_oiio = n_ixxi - n_iiii - o_ioii - o_iioi
    o_oooi = (n_xxxi - n_iiii - o_oiii - o_ioii - o_iioi - o_ooii - o_oioi -
        o_iooi)
    o_ooio = (n_xxix - n_iiii - o_oiii - o_ioii - o_iiio - o_ooii - o_oiio -
        o_ioio)
    o_oioo = (n_xixx - n_iiii - o_oiii - o_iioi - o_iiio - o_oioi - o_iioo -
        o_oiio)
    o_iooo = (n_ixxx - n_iiii - o_ioii - o_iioi - o_iiio - o_iooi - o_iioo -
        o_ioio)
    o_oooo = (n_xxxx - n_iiii - o_oiii - o_ioii - o_iioi - o_iiio - o_ooii -
        o_iooi - o_iioo - o_oioi - o_ioio - o_oiio - o_oooi - o_ooio -
        o_oioo - o_iooo)
    return (o_iiii, o_oiii, o_ioii, o_iioi, o_iiio, o_ooii, o_iooi, o_iioo,
        o_oioi, o_ioio, o_oiio, o_oooi, o_ooio, o_oioo, o_iooo, o_oooo)


def expected4(observed):
    (o_iiii, o_oiii, o_ioii, o_iioi, o_iiio, o_ooii, o_iooi, o_iioo, o_oioi,
        o_ioio, o_oiio, o_oooi, o_ooio, o_oioo, o_iooo, o_oooo) = observed
    n_xxxx = float(o_iiii + o_oiii + o_ioii + o_iioi + o_iiio + o_ooii +
        o_iooi + o_iioo + o_oioi + o_ioio + o_oiio + o_oooi + o_ooio +
        o_oioo + o_iooo + o_oooo)
    e_iiii = (o_iiii + o_oiii) * (o_iiii + o_ioii) * (o_iiii + o_iioi) * (
        o_iiii + o_iiio) / n_xxxx
    e_oiii = (o_oiii + o_iiii) * (o_oiii + o_ooii) * (o_oiii + o_oioi) * (
        o_oiii + o_oiio) / n_xxxx
    e_ioii = (o_ioii + o_ooii) * (o_ioii + o_iiii) * (o_ioii + o_iooi) * (
        o_ioii + o_ioio) / n_xxxx
    e_iioi = (o_iioi + o_oioi) * (o_iioi + o_iooi) * (o_iioi + o_iiii) * (
        o_iioi + o_iioo) / n_xxxx
    e_iiio = (o_iiio + o_oiio) * (o_iiio + o_ioio) * (o_iiio + o_iioo) * (
        o_iiio + o_iiii) / n_xxxx
    e_ooii = (o_ooii + o_ioii) * (o_ooii + o_oiii) * (o_ooii + o_oooi) * (
        o_ooii + o_ooio) / n_xxxx
    e_oioi = (o_oioi + o_iioi) * (o_oioi + o_oooi) * (o_oioi + o_oiii) * (
        o_oioi + o_oioo) / n_xxxx
    e_oiio = (o_oiio + o_iiio) * (o_oiio + o_ooio) * (o_oiio + o_oioo) * (
        o_oiio + o_oiii) / n_xxxx
    e_iooi = (o_iooi + o_oooi) * (o_iooi + o_iioi) * (o_iooi + o_ioii) * (
        o_iooi + o_iooo) / n_xxxx
    e_ioio = (o_ioio + o_ooio) * (o_ioio + o_iiio) * (o_ioio + o_iooo) * (
        o_ioio + o_ioii) / n_xxxx
    e_iioo = (o_iioo + o_oioo) * (o_iioo + o_iooo) * (o_iioo + o_iiio) * (
        o_iioo + o_iioi) / n_xxxx
    e_oooi = (o_oooi + o_iooi) * (o_oooi + o_oioi) * (o_oooi + o_ooii) * (
        o_oooi + o_oooo) / n_xxxx
    e_ooio = (o_ooio + o_ioio) * (o_ooio + o_oiio) * (o_ooio + o_oooo) * (
        o_ooio + o_ooii) / n_xxxx
    e_oioo = (o_oioo + o_iioo) * (o_oioo + o_oooo) * (o_oioo + o_oiio) * (
        o_oioo + o_oioi) / n_xxxx
    e_iooo = (o_iooo + o_oooo) * (o_iooo + o_iioo) * (o_iooo + o_ioio) * (
        o_iooo + o_iooi) / n_xxxx
    e_oooo = (o_oooo + o_iooo) * (o_oooo + o_oioo) * (o_oooo + o_ooio) * (
        o_oooo + o_oooi) / n_xxxx
    return (e_iiii, e_oiii, e_ioii, e_iioi, e_iiio, e_ooii, e_iooi, e_iioo,
        e_oioi, e_ioio, e_oiio, e_oooi, e_ooio, e_oioo, e_iooo, e_oooo)


def create_ngram_star(lemmas):
    from itertools import product
    ngrams = []
    for logical_vector in product((True, False), repeat=ngram_length):
        logical_ngram = ['*' for e in range(ngram_length)]
        for index, logical_value in enumerate(logical_vector):
            if logical_value:
                logical_ngram[index] = lemmas[index]
        ngrams.append(tuple(logical_ngram))
    return ngrams


<mask token>


def avg_idf(ngram):
    max_idf = max(idf.values())
    avg_idf = 0.0
    for lemma in ngram:
        avg_idf += idf.get(lemma, max_idf)
    return avg_idf / len(ngram)


def calculate_tfidf(ngram_frequency_distr):
    result = []
    ngram_probability = relativize_distr(ngram_frequency_distr)
    for ngram, tf in ngram_probability.iteritems():
        if ngram_frequency_distr[ngram] >= min_frequency:
            idf_avg = 0.0
            result.append((tf * avg_idf(ngram), ngram))
    return sorted(result, reverse=True)


def relativize_distr(distr):
    copy_distr = {}
    all = float(sum(distr.values()))
    for key, value in distr.iteritems():
        copy_distr[key] = distr[key] / all
    return copy_distr


<mask token>


def parse_arguments():
    key = None
    for argument in sys.argv[1:]:
        if argument.startswith('-'):
            key = argument[1:]
            if key == 'h':
                print_help()
            if key not in definable_properties:
                sys.stderr.write('Warning: argument identifier ' + argument +
                    ' unknown\n')
            else:
                properties[key] = []
        elif key is None:
            sys.stderr.write('Warning: argument ' + argument +
                ' without argument identifier' + '\n')
        elif key in definable_properties:
            properties[key].append(argument)
        else:
            sys.stderr.write('Error: unknown argument identifier ' + key + '\n'
                )
            print_help()


def print_help():
    sys.stderr.write('Syntax:\n')
    sys.stderr.write(
        """python CollTerm.py -i input_file -p phrase_configuration_file -m ngram_ranking_method -l length_of_ngrams
"""
        )
    sys.stderr.write('Arguments:\n')
    sys.stderr.write('-i\ttab separated input file\n')
    sys.stderr.write('-p\tphrase configuration file\n')
    sys.stderr.write('\t\t- symbols for defining stop word phrases:\n')
    sys.stderr.write('\t\t\t- !STOP - non-stop word\n')
    sys.stderr.write('\t\t\t- STOP - stop word\n')
    sys.stderr.write('\t\t\t- * - any word\n')
    sys.stderr.write('\t\t- bigram example: STOP\t*\n')
    sys.stderr.write('-s\tstop word file\n')
    sys.stderr.write('-n\tmaximum number of top ranked terms\n')
    sys.stderr.write('-t\tthreshold (minimum score)\n')
    sys.stderr.write('-m\tn-gram ranking method\n')
    sys.stderr.write('\t\tdice - Dice coefficient\n')
    sys.stderr.write('\t\tmi - modified mutual information\n')
    sys.stderr.write('\t\tchisq - chi-square statistic\n')
    sys.stderr.write('\t\tll - log-likelihood ratio\n')
    sys.stderr.write('\t\ttscore - t-score\n')
    sys.stderr.write('\t\ttfidf - tf-idf score (with a mandatory idf file)\n')
    sys.stderr.write(
        '-l\tlength of n-grams to be extracted (0-4, 0 for all length n-grams)\n'
        )
    sys.stderr.write(
        '-o\textracted term list output file (if not given, stdout used)\n')
    sys.stderr.write(
        '-pos\tpositions of tokens, POS tags and lemmas (zero-based indices)\n'
        )
    sys.stderr.write(
        '-min\tminimum frequency of n-grams taken in consideration\n')
    sys.stderr.write('-prop\tproperty file\n')
    sys.stderr.write(
        """-idf	idf file (mandatory for tfidf, in case of other ranking methods a linear combination is computed)
"""
        )
    sys.stderr.write(
        """-seq	output n-grams as a sequence of 0 - lemmata n-grams, 1 - most frequent token n-grams, 2 - lemmata n-grams + most frequent token n-grams, 3 - all token n-grams with their frequencies
"""
        )
    sys.stderr.write('-norm\tnormalize output to a [0,x] range\n')
    sys.stderr.write('-terms\toutput terms as\n')
    sys.stderr.write('\t\t0 - terms and weights (+ frequency if "-seq 2")\n')
    sys.stderr.write('\t\t1 - terms only\n')
    sys.exit(1)


def check_properties():
    global term_number
    term_number = None
    global threshold
    threshold = None
    global ranking_method
    global ngram_length
    global output_file
    global position
    global min_frequency
    global seq
    seq = 0
    global norm
    norm = 0
    global terms
    terms = 0
    if 'prop' in properties:
        if properties['prop'] == []:
            sys.stderr.write(
                'Error: no argument given for property file (-prop)\n')
            print_help()
        import re
        line_re = re.compile('(.+?)=(.+)')
        try:
            properties_file = open(properties['prop'][-1])
        except:
            sys.stderr.write('Error: can not open property file (-prop): ' +
                properties['prop'][-1] + '\n')
            print_help()
        i = 0
        for line in properties_file:
            i += 1
            if line.strip().startswith('#'):
                continue
            result = line_re.search(line)
            if result is None:
                sys.stderr.write('Error in property file line ' + str(i) +
                    '\n' + repr(line) + '\n')
                print_help()
            key = result.group(1).strip()
            if '"' in line:
                values = re.findall('"(.+?)"', result.group(2).strip())
            else:
                values = re.split('\\s+', result.group(2).strip())
            if key not in definable_properties:
                sys.stderr.write('Error: unknown argument identifier ' +
                    key + """ (property file)
""")
                print_help()
            properties[key] = values
    missing_properties = mandatory_properties.difference(mandatory_properties
        .intersection(properties))
    if len(missing_properties) > 0:
        sys.stderr.write('Error: these mandatory properties are missing: ' +
            ', '.join(missing_properties) + '\n')
        print_help()
    if 'n' in properties:
        if properties['n'] == []:
            sys.stderr.write(
                'Error: no argument given for number of terms (-n)\n')
            print_help()
        try:
            term_number = int(properties['n'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument for number of terms (-n): ' +
                properties['n'][-1] + '\n')
            print_help()
    if 't' in properties:
        if properties['t'] == []:
            sys.stderr.write('Error: no argument given for threshold (-t)\n')
            print_help()
        try:
            threshold = float(properties['t'][-1])
        except:
            sys.stderr.write('Error: wrong argument for threshold (-t): ' +
                properties['t'][-1] + '\n')
            print_help()
    if properties['m'] == []:
        sys.stderr.write(
            'Error: no argument given for n-gram ranking method (-m)\n')
        print_help()
    ranking_method = properties['m'][-1]
    if ranking_method not in ranking_methods:
        sys.stderr.write(
            'Error: wrong argument for n-gram ranking method (-m): ' +
            ranking_method + '\n')
        print_help()
    if properties['l'] == []:
        sys.stderr.write(
            'Error: no argument given for length of n-grams (-l)\n')
        print_help()
    try:
        ngram_length = int(properties['l'][-1])
        if ngram_length < 1 or ngram_length > 4:
            raise Exception
    except:
        sys.stderr.write(
            'Error: wrong argument for length of n-grams (-l): ' +
            properties['l'][-1] + '\n')
        print_help()
    if ngram_length == 1 and 'idf' not in properties:
        sys.stderr.write(
            'Error: idf file has to be defined for length of n-grams 1 (-l 1)\n'
            )
        print_help()
    if 'o' in properties:
        if properties['o'] == []:
            sys.stderr.write('Error: no argument given output file (-o)\n')
            print_help()
        try:
            output_file = open(properties['o'][-1], 'w')
        except:
            sys.stderr.write('Error: can not write to output file ' +
                properties['o'][-1] + '\n')
            print_help()
    else:
        output_file = sys.stdout
    if 'pos' in properties:
        if len(properties['pos']) < 3:
            sys.stderr.write(
                'Error: wrong number of arguments given for position (-pos)\n')
            print_help()
        try:
            position = [int(e) for e in properties['pos'][-3:]]
            if len(set(position)) != 3:
                raise Exception
        except:
            sys.stderr.write(
                'Error: wrong arguments given for position (-pos): ' + ', '
                .join(properties['pos'][-3:]) + '\n')
            print_help()
    else:
        position = range(3)
    if 'min' in properties:
        if properties['min'] == []:
            sys.stderr.write(
                'Error: no argument given for minimum frequency (-min)\n')
            print_help()
        try:
            min_frequency = int(properties['min'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument given for minimum frequency (-min): ' +
                properties['min'][-1] + '\n')
            print_help()
    if 'idf' in properties:
        if properties['idf'] == []:
            sys.stderr.write('Error: no argument given for idf file (-idf)\n')
            print_help()
    if 'seq' in properties:
        if properties['seq'] == []:
            sys.stderr.write(
                'Error: no argument given for sequence output (-seq)\n')
            print_help()
        if properties['seq'][-1] != '0' and properties['seq'][-1
            ] != '1' and properties['seq'][-1] != '2':
            sys.stderr.write(
                'Error: wrong argument given for sequence output (-seq): ' +
                properties['seq'][-1] + '\n')
            print_help()
        seq = int(properties['seq'][-1])
    if 'norm' in properties:
        if properties['norm'] == []:
            sys.stderr.write(
                'Error: no argument given for normalization (-norm)\n')
            print_help()
        try:
            norm = float(properties['norm'][-1])
        except:
            sys.stderr.write(
                'Error: wrong argument given for normalization (-norm): ' +
                properties['norm'][-1] + '\n')
            print_help()
    if 'terms' in properties:
        if properties['terms'] == []:
            sys.stderr.write(
                'Error: no argument given for term output (-terms)\n')
            print_help()
        if properties['terms'][-1] != '0' and properties['terms'][-1] != '1':
            sys.stderr.write(
                'Error: wrong argument given for term output (-terms): ' +
                properties['terms'][-1] + '\n')
            print_help()
        terms = int(properties['terms'][-1])


def read_phrase_configuration_file():
    global valid_phrases
    valid_phrases = []
    global stop_phrase
    stop_phrase = []
    global ngram_length
    if properties['p'] == []:
        sys.stderr.write(
            'Error: no argument given for phrase configuration file (-p)\n')
        print_help()
    try:
        phrase_configuration_file = open(properties['p'][-1], 'r')
    except:
        sys.stderr.write('Error: can not read phrase configuration file ' +
            properties['p'][-1] + '\n')
        print_help()
    i = 0
    for line in phrase_configuration_file:
        i += 1
        if line.strip().startswith('#'):
            continue
        if line.strip() == '':
            continue
        valid_phrase = line.strip().split('\t')
        try:
            if ngram_length != len(valid_phrase):
                continue
            if 'STOP' in line:
                if stop_phrase != []:
                    raise Exception
                for stop in valid_phrase:
                    if stop not in ('!STOP', 'STOP', '*'):
                        raise Exception
                stop_phrase = valid_phrase
                continue
            valid_phrase = [re.compile(e) for e in valid_phrase]
        except:
            sys.stderr.write('Error in phrase configuration file line ' +
                str(i) + '\n' + repr(line) + '\n')
            print_help()
        valid_phrases.append(valid_phrase)


def read_stopword_file():
    global stopwords
    stopwords = set()
    if 's' not in properties:
        return
    if properties['s'] == []:
        sys.stderr.write('Error: no argument given for stop-word file (-s)\n')
        print_help()
    try:
        stopwords = set([e.strip() for e in codecs.open(properties['s'][-1],
            'r', 'utf-8')])
    except:
        sys.stderr.write('Error: can not read stop-word file ' + properties
            ['s'][-1] + '\n')
        print_help()


def read_idf_file():
    if 'idf' not in properties:
        return
    global idf
    idf = {}
    if properties['idf'] == []:
        sys.stderr.write('Error: no argument given for idf file (-idf)\n')
        print_help()
    try:
        idf = dict([(a, float(b)) for a, b in [e.split('\t') for e in
            codecs.open(properties['idf'][-1], 'r', 'utf-8')]])
    except:
        sys.stderr.write('Error: can not read idf file ' + properties['idf'
            ][-1] + '\n')
        print_help()


def read_input_text():
    enamex = 0
    numex = 0
    timex = 0
    if properties['i'] == []:
        sys.stderr.write('Error: no argument given for input file (-i)\n')
        print_help()
    path = properties['i'][-1]
    try:
        input_file = codecs.open(path, 'r', 'utf-8')
    except:
        sys.stderr.write('Error: can not read input file ' + path + '\n')
        print_help()
    i = 0
    ngram = [None for e in range(ngram_length)]
    global ngram_frequency_distr
    ngram_frequency_distr = {}
    global unigram_frequency_distr
    unigram_frequency_distr = {}
    global lemma_token_frequency_distr
    lemma_token_frequency_distr = {}
    global lemma_phrase_map
    lemma_phrase_map = {}
    for line in input_file:
        if i == 0:
            if line.startswith(u'\ufeff'):
                line = line[1:]
        i += 1
        split_line = line.strip().split('\t')
        if split_line == ['']:
            continue
        if split_line[0][0] == '<':
            if split_line[0].startswith('<NUMEX'):
                numex += 1
            elif split_line[0].startswith('<ENAMEX'):
                enamex += 1
            elif split_line[0].startswith('<TIMEX'):
                timex += 1
            elif split_line[0].startswith('</NUMEX'):
                numex -= 1
            elif split_line[0].startswith('</ENAMEX'):
                enamex -= 1
            elif split_line[0].startswith('</TIMEX'):
                timex -= 1
            else:
                continue
            ngram = [None for e in range(ngram_length)]
            if enamex < 0 or numex < 0 or timex < 0:
                sys.stderr.write(
                    'Error: closing bracket without open on line ' + str(i) +
                    '\n' + repr(line) + '\n')
                sys.exit(1)
            continue
        if enamex != 0 or numex != 0 or timex != 0:
            continue
        try:
            token, pos, lemma = split_line[position[0]], split_line[position[1]
                ], split_line[position[2]]
            token = token.lower()
            lemma = lemma.lower()
        except:
            sys.stderr.write('Error in input file line ' + str(i) + '\n' +
                repr(line) + '\n')
            print_help()
        if ranking_method in ('dice', 'mi'):
            unigram_frequency_distr[lemma] = unigram_frequency_distr.get(lemma,
                0) + 1
        ngram = ngram[1:]
        ngram.append((token, pos, lemma))
        try:
            tokens = tuple([e[0] for e in ngram])
            poses = tuple([e[1] for e in ngram])
            lemmas = tuple([e[2] for e in ngram])
        except:
            continue
        if ranking_method in ('ll', 'chisq', 'tscore'):
            for star_ngram in create_ngram_star(lemmas):
                ngram_frequency_distr[star_ngram] = ngram_frequency_distr.get(
                    star_ngram, 0) + 1
        phrase = check_ngram_for_phrases(poses)
        if phrase != None and check_ngram_for_stops(tokens):
            if lemmas not in lemma_phrase_map:
                lemma_phrase_map[lemmas] = {}
            lemma_phrase_map[lemmas][phrase] = lemma_phrase_map[lemmas].get(
                phrase, 0) + 1
            if ranking_method in ('dice', 'mi', 'tfidf'):
                ngram_frequency_distr[lemmas] = ngram_frequency_distr.get(
                    lemmas, 0) + 1
            if lemmas not in lemma_token_frequency_distr:
                lemma_token_frequency_distr[lemmas] = {}
            lemma_token_frequency_distr[lemmas][tokens
                ] = lemma_token_frequency_distr[lemmas].get(tokens, 0) + 1
    global results
    if ranking_method in ('dice', 'mi'):
        results = ranking_methods[ranking_method](ngram_frequency_distr,
            unigram_frequency_distr)
    elif ranking_method in ('ll', 'chisq', 'tscore', 'tfidf'):
        results = ranking_methods[ranking_method](ngram_frequency_distr)


def check_ngram_for_phrases(pos_ngram):
    for phrase in valid_phrases:
        valid = True
        for pos, regex in zip(pos_ngram, phrase):
            if pos is None:
                valid = False
                break
            if regex.match(pos) is None:
                valid = False
                break
        if valid:
            return ' '.join([e.pattern for e in phrase])


def check_ngram_for_stops(token_ngram):
    if stop_phrase == []:
        return True
    for token, stop in zip(token_ngram, stop_phrase):
        if stop == 'STOP' and token not in stopwords:
            return False
        elif stop == '!STOP' and token in stopwords:
            return False
    return True


def normalize_result():
    global results
    global norm
    if norm == 0:
        norm = 1
    values = [a for a, b in results]
    if len(values) == 0:
        return
    min_value = min(values)
    max_value = max(values)
    range = float(max_value - min_value)
    for index, (value, ngram) in enumerate(results):
        try:
            results[index] = norm * (value - min_value) / range, ngram
        except ZeroDivisionError:
            results[index] = norm, ngram


def linearly_combine_with_idf():
    normalize_result()
    global results
    results = sorted([(value * 0.5 + avg_idf(ngram) * 0.5, ngram) for value,
        ngram in results], reverse=True)


def output_result():
    i = 0
    for value, ngram in results:
        if threshold is not None:
            if value < threshold:
                break
        if seq == 0:
            output = ' '.join(ngram).encode('utf-8') + '\t(' + '|'.join([e[
                0] for e in sorted(lemma_phrase_map[ngram].items(), key=lambda
                x: -x[1])]) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        elif seq == 1:
            output = ' '.join(sorted(lemma_token_frequency_distr[ngram].
                items(), key=lambda x: x[1])[-1][0]).encode('utf-8'
                ) + '\t(' + '|'.join([e[0] for e in sorted(lemma_phrase_map
                [ngram].items(), key=lambda x: -x[1])]) + ', ' + str(
                ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        elif seq == 2:
            output = ' '.join(ngram).encode('utf-8') + '\t' + ' '.join(sorted
                (lemma_token_frequency_distr[ngram].items(), key=lambda x:
                x[1])[-1][0]).encode('utf-8') + '\t(' + '|'.join([e[0] for
                e in sorted(lemma_phrase_map[ngram].items(), key=lambda x: 
                -x[1])]) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
            if terms == 0:
                output += '\t' + str(round(value, 5))
            output_file.write(output + '\n')
        else:
            for token_sequence, frequency in lemma_token_frequency_distr[ngram
                ].iteritems():
                output = ' '.join(token_sequence).encode('utf-8'
                    ) + '\t(' + '|'.join([e[0] for e in sorted(
                    lemma_phrase_map[ngram].items(), key=lambda x: -x[1])]
                    ) + ', ' + str(ngram_frequency_distr[ngram]) + ')'
                if terms == 0:
                    output += '\t' + str(frequency) + '\t' + str(round(
                        value, 5))
                output_file.write(output + '\n')
        i += 1
        if term_number is not None:
            if i >= term_number:
                break


<mask token>

#!/usr/bin/python
import sys
import codecs
import re

def calculate_g0_dice(ngram_frequency_distr,unigram_frequency_distr):
	result=[]
	for ngram in ngram_frequency_distr:
		if ngram_frequency_distr[ngram]>=min_frequency: #minimum frequency
			result.append((float(ngram_length)*ngram_frequency_distr[ngram]/sum([unigram_frequency_distr[e] for e in ngram]),ngram))
	return sorted(result,reverse=True)

def calculate_g0_mi(ngram_frequency_distr,unigram_frequency_distr):
	result=[]
	ngram_probability=relativize_distr(ngram_frequency_distr)
	unigram_probability=relativize_distr(unigram_frequency_distr)
	from math import log
	for ngram in ngram_probability:
		if ngram_frequency_distr[ngram]>=min_frequency: # minimum frequency
			#result.append((log(ngram_frequency_distr[ngram]*ngram_probability[ngram]/product([unigram_probability[e] for e in ngram])),ngram))
			result.append(((log(ngram_probability[ngram]/product([unigram_probability[e] for e in ngram]))),ngram))
	return sorted(result,reverse=True)

def calculate_g0_ll(ngram_frequency):
	result=[]
	from math import log
	observed_functions=[observed2,observed3,observed4]
	expected_functions=[expected2,expected3,expected4]
	for ngram in lemma_token_frequency_distr:
		if ngram_frequency[ngram]>=min_frequency:
			marginals=[ngram_frequency[e] for e in create_ngram_star(ngram)]
			observed=observed_functions[ngram_length-2](marginals)
			expected=expected_functions[ngram_length-2](observed)
			ll=0.0
			for o,e in zip(observed,expected):
				try:
					ll+=o*log(o/e)
				except:
					pass
			result.append((2*ll,ngram))
	return sorted(result,reverse=True)

def calculate_g0_chisq(ngram_frequency):
	result=[]
	observed_functions=[observed2,observed3,observed4]
	expected_functions=[expected2,expected3,expected4]
	for ngram in lemma_token_frequency_distr:
		if ngram_frequency[ngram]>=min_frequency:
			marginals=[ngram_frequency[e] for e in create_ngram_star(ngram)]
			observed=observed_functions[ngram_length-2](marginals)
			expected=expected_functions[ngram_length-2](observed)
			chisq=0.0
			for o,e in zip(observed,expected):
				try:
					chisq+=(o-e)**2/e
				except:
					pass
			result.append((chisq,ngram))
	return sorted(result,reverse=True)

def calculate_g0_tscore(ngram_frequency):
	from math import sqrt
	result=[]
	observed_functions=[observed2,observed3,observed4]
	expected_functions=[expected2,expected3,expected4]
	for ngram in lemma_token_frequency_distr:
		if ngram_frequency[ngram]>=min_frequency:
			marginals=[ngram_frequency[e] for e in create_ngram_star(ngram)]
			observed=observed_functions[ngram_length-2](marginals)
			expected=expected_functions[ngram_length-2](observed)
			tscore=float(observed[0]-expected[0])/sqrt(expected[0])
			result.append((tscore,ngram))
	return sorted(result,reverse=True)

def observed2(marginals):
	n_ii,n_ix,n_xi,n_xx=marginals
	n_oi = n_xi - n_ii
	n_io = n_ix - n_ii
	return (n_ii, n_io, n_oi, n_xx - n_ii - n_oi - n_io)

def expected2(observed):
	n_ii, n_io, n_oi, n_oo=observed
	n_xx = float(n_ii+n_oi+n_io+n_oo)
	e_ii=(n_ii+n_io)*(n_ii+n_oi)/n_xx
	e_io=(n_ii+n_io)*(n_io+n_oo)/n_xx
	e_oi=(n_oi+n_oo)*(n_ii+n_oi)/n_xx
	e_oo=(n_oi+n_oo)*(n_io+n_oo)/n_xx
	return (e_ii,e_io,e_oi,e_oo) 
	
def expected_nltk(contingency):
	n_xx=sum(contingency)
	for i in range(4): 
		yield (contingency[i] + contingency[i ^ 1]) * (contingency[i] + contingency[i ^ 2]) / float(n_xx)

def observed3(marginals):
	n_iii,n_iix,n_ixi,n_ixx,n_xii,n_xix,n_xxi,n_xxx=marginals
	n_oii = n_xii - n_iii
	n_ioi = n_ixi - n_iii 
	n_iio = n_iix - n_iii 
	n_ooi = n_xxi - n_iii - n_oii - n_ioi
	n_oio = n_xix - n_iii - n_oii - n_iio 
	n_ioo = n_ixx - n_iii - n_ioi - n_iio 
	n_ooo = n_xxx - n_iii - n_oii - n_ioi - n_iio - n_ooi - n_oio - n_ioo 
	return (n_iii, n_iio, n_ioi, n_oii, n_ioo, n_ooi, n_oio, n_ooo)

def expected3(observed):
	o_iii, o_iio, o_ioi, o_oii, o_ioo, o_ooi, o_oio, o_ooo=observed
	n_xxx=float(o_iii+o_iio+o_ioi+o_oii+o_ioo+o_ooi+o_oio+o_ooo)
	e_iii=(o_iii+o_oii)*(o_iii+o_ioi)*(o_iii+o_iio)/n_xxx
	e_iio=(o_iio+o_oio)*(o_iio+o_ioi)*(o_iio+o_iii)/n_xxx
	e_ioi=(o_ioi+o_ooi)*(o_ioi+o_iii)*(o_ioi+o_ioo)/n_xxx
	e_oii=(o_oii+o_iii)*(o_oii+o_ooi)*(o_oii+o_oio)/n_xxx
	e_ioo=(o_ioo+o_ooo)*(o_ioo+o_iio)*(o_ioo+o_ioi)/n_xxx
	e_ooi=(o_ooi+o_ioi)*(o_ooi+o_oii)*(o_ooi+o_ooo)/n_xxx
	e_oio=(o_oio+o_iio)*(o_oio+o_ooo)*(o_oio+o_oii)/n_xxx
	e_ooo=(o_ooo+o_ioo)*(o_ooo+o_oio)*(o_ooo+o_ooi)/n_xxx
	return (e_iii,e_iio,e_ioi,e_oii,e_ioo,e_ooi,e_oio,e_ooo)

def observed4(marginals):
	n_iiii,n_xiii,n_ixii,n_iixi,n_iiix,n_xxii,n_ixxi,n_iixx,n_xixi,n_xiix,n_ixix,n_xxxi,n_xxix,n_xixx,n_ixxx,n_xxxx=marginals
	o_iiii=n_iiii
	o_oiii=n_xiii-n_iiii
	o_ioii=n_ixii-n_iiii
	o_iioi=n_iixi-n_iiii
	o_iiio=n_iiix-n_iiii
	o_ooii=n_xxii-n_iiii-o_oiii-o_ioii
	o_iooi=n_ixxi-n_iiii-o_ioii-o_iioi
	o_iioo=n_iixx-n_iiii-o_iioi-o_iiio
	o_oioi=n_xixi-n_iiii-o_oiii-o_iioi
	o_ioio=n_ixix-n_iiii-o_ioii-o_iiio
	o_oiio=n_ixxi-n_iiii-o_ioii-o_iioi
	o_oooi=n_xxxi-n_iiii-o_oiii-o_ioii-o_iioi-o_ooii-o_oioi-o_iooi
	o_ooio=n_xxix-n_iiii-o_oiii-o_ioii-o_iiio-o_ooii-o_oiio-o_ioio
	o_oioo=n_xixx-n_iiii-o_oiii-o_iioi-o_iiio-o_oioi-o_iioo-o_oiio
	o_iooo=n_ixxx-n_iiii-o_ioii-o_iioi-o_iiio-o_iooi-o_iioo-o_ioio
	o_oooo=n_xxxx-n_iiii-o_oiii-o_ioii-o_iioi-o_iiio-o_ooii-o_iooi-o_iioo-o_oioi-o_ioio-o_oiio-o_oooi-o_ooio-o_oioo-o_iooo
	return (o_iiii,o_oiii,o_ioii,o_iioi,o_iiio,o_ooii,o_iooi,o_iioo,o_oioi,o_ioio,o_oiio,o_oooi,o_ooio,o_oioo,o_iooo,o_oooo)

def expected4(observed):
	o_iiii,o_oiii,o_ioii,o_iioi,o_iiio,o_ooii,o_iooi,o_iioo,o_oioi,o_ioio,o_oiio,o_oooi,o_ooio,o_oioo,o_iooo,o_oooo=observed
	n_xxxx=float(o_iiii+o_oiii+o_ioii+o_iioi+o_iiio+o_ooii+o_iooi+o_iioo+o_oioi+o_ioio+o_oiio+o_oooi+o_ooio+o_oioo+o_iooo+o_oooo)
	e_iiii=(o_iiii+o_oiii)*(o_iiii+o_ioii)*(o_iiii+o_iioi)*(o_iiii+o_iiio)/n_xxxx
	e_oiii=(o_oiii+o_iiii)*(o_oiii+o_ooii)*(o_oiii+o_oioi)*(o_oiii+o_oiio)/n_xxxx
	e_ioii=(o_ioii+o_ooii)*(o_ioii+o_iiii)*(o_ioii+o_iooi)*(o_ioii+o_ioio)/n_xxxx
	e_iioi=(o_iioi+o_oioi)*(o_iioi+o_iooi)*(o_iioi+o_iiii)*(o_iioi+o_iioo)/n_xxxx
	e_iiio=(o_iiio+o_oiio)*(o_iiio+o_ioio)*(o_iiio+o_iioo)*(o_iiio+o_iiii)/n_xxxx
	e_ooii=(o_ooii+o_ioii)*(o_ooii+o_oiii)*(o_ooii+o_oooi)*(o_ooii+o_ooio)/n_xxxx
	e_oioi=(o_oioi+o_iioi)*(o_oioi+o_oooi)*(o_oioi+o_oiii)*(o_oioi+o_oioo)/n_xxxx
	e_oiio=(o_oiio+o_iiio)*(o_oiio+o_ooio)*(o_oiio+o_oioo)*(o_oiio+o_oiii)/n_xxxx
	e_iooi=(o_iooi+o_oooi)*(o_iooi+o_iioi)*(o_iooi+o_ioii)*(o_iooi+o_iooo)/n_xxxx
	e_ioio=(o_ioio+o_ooio)*(o_ioio+o_iiio)*(o_ioio+o_iooo)*(o_ioio+o_ioii)/n_xxxx
	e_iioo=(o_iioo+o_oioo)*(o_iioo+o_iooo)*(o_iioo+o_iiio)*(o_iioo+o_iioi)/n_xxxx
	e_oooi=(o_oooi+o_iooi)*(o_oooi+o_oioi)*(o_oooi+o_ooii)*(o_oooi+o_oooo)/n_xxxx
	e_ooio=(o_ooio+o_ioio)*(o_ooio+o_oiio)*(o_ooio+o_oooo)*(o_ooio+o_ooii)/n_xxxx
	e_oioo=(o_oioo+o_iioo)*(o_oioo+o_oooo)*(o_oioo+o_oiio)*(o_oioo+o_oioi)/n_xxxx
	e_iooo=(o_iooo+o_oooo)*(o_iooo+o_iioo)*(o_iooo+o_ioio)*(o_iooo+o_iooi)/n_xxxx
	e_oooo=(o_oooo+o_iooo)*(o_oooo+o_oioo)*(o_oooo+o_ooio)*(o_oooo+o_oooi)/n_xxxx
	return (e_iiii,e_oiii,e_ioii,e_iioi,e_iiio,e_ooii,e_iooi,e_iioo,e_oioi,e_ioio,e_oiio,e_oooi,e_ooio,e_oioo,e_iooo,e_oooo)

def create_ngram_star(lemmas):
	from itertools import product
	ngrams=[]
	for logical_vector in product((True,False),repeat=ngram_length):
		logical_ngram=['*' for e in range(ngram_length)]
		for index,logical_value in enumerate(logical_vector):
			if logical_value:
				logical_ngram[index]=lemmas[index]
		ngrams.append(tuple(logical_ngram))
	return ngrams

product=lambda s: reduce(lambda x, y: x * y, s)

def avg_idf(ngram):
	max_idf=max(idf.values())
	
	avg_idf=0.0
	for lemma in ngram:
		avg_idf+=idf.get(lemma,max_idf)
	return avg_idf/len(ngram)

def calculate_tfidf(ngram_frequency_distr):
	result=[]
	ngram_probability=relativize_distr(ngram_frequency_distr)
	for ngram,tf in ngram_probability.iteritems():
		if ngram_frequency_distr[ngram]>=min_frequency:
			idf_avg=0.0
			result.append((tf*avg_idf(ngram),ngram))
	return sorted(result,reverse=True)

def relativize_distr(distr):
	copy_distr={}
	all=float(sum(distr.values()))
	for key,value in distr.iteritems():
		copy_distr[key]=distr[key]/all
	return copy_distr

min_frequency=3
optional_properties=set(['h','s','n','t','o','pos','prop','min','idf','seq','norm','terms'])
mandatory_properties=set(['i','p','m','l'])
definable_properties=optional_properties.union(mandatory_properties)
properties={}
ranking_methods={'dice':calculate_g0_dice,'mi':calculate_g0_mi,'ll':calculate_g0_ll,'chisq':calculate_g0_chisq,'tscore':calculate_g0_tscore,'tfidf':calculate_tfidf}

def parse_arguments():
	key=None
	for argument in sys.argv[1:]:
		if argument.startswith('-'):
			key=argument[1:]
			if key=='h':
				print_help()
			if key not in definable_properties:
				sys.stderr.write('Warning: argument identifier '+argument+' unknown\n')
			else:
				properties[key]=[]
		elif key is None:
			sys.stderr.write('Warning: argument '+argument+' without argument identifier'+'\n')
		elif key in definable_properties:
			properties[key].append(argument)
		else:
			sys.stderr.write('Error: unknown argument identifier '+key+'\n')
			print_help()

def print_help():
	sys.stderr.write('Syntax:\n')
	sys.stderr.write('python CollTerm.py -i input_file -p phrase_configuration_file -m ngram_ranking_method -l length_of_ngrams\n')
	sys.stderr.write('Arguments:\n')
	sys.stderr.write('-i\ttab separated input file\n')
	sys.stderr.write('-p\tphrase configuration file\n')
	sys.stderr.write('\t\t- symbols for defining stop word phrases:\n')
	sys.stderr.write('\t\t\t- !STOP - non-stop word\n')
	sys.stderr.write('\t\t\t- STOP - stop word\n')
	sys.stderr.write('\t\t\t- * - any word\n')
	sys.stderr.write('\t\t- bigram example: STOP	*\n')
	sys.stderr.write('-s\tstop word file\n')
	sys.stderr.write('-n\tmaximum number of top ranked terms\n')
	sys.stderr.write('-t\tthreshold (minimum score)\n')
	sys.stderr.write('-m\tn-gram ranking method\n')
	sys.stderr.write('\t\tdice - Dice coefficient\n')
	sys.stderr.write('\t\tmi - modified mutual information\n')
	sys.stderr.write('\t\tchisq - chi-square statistic\n')
	sys.stderr.write('\t\tll - log-likelihood ratio\n')
	sys.stderr.write('\t\ttscore - t-score\n')
	sys.stderr.write('\t\ttfidf - tf-idf score (with a mandatory idf file)\n')
	sys.stderr.write('-l\tlength of n-grams to be extracted (0-4, 0 for all length n-grams)\n')
	sys.stderr.write('-o\textracted term list output file (if not given, stdout used)\n')
	sys.stderr.write('-pos\tpositions of tokens, POS tags and lemmas (zero-based indices)\n')
	sys.stderr.write('-min\tminimum frequency of n-grams taken in consideration\n')
	sys.stderr.write('-prop\tproperty file\n')
	sys.stderr.write('-idf\tidf file (mandatory for tfidf, in case of other ranking methods a linear combination is computed)\n')
	sys.stderr.write('-seq\toutput n-grams as a sequence of 0 - lemmata n-grams, 1 - most frequent token n-grams, 2 - lemmata n-grams + most frequent token n-grams, 3 - all token n-grams with their frequencies\n')
	sys.stderr.write('-norm\tnormalize output to a [0,x] range\n')
	sys.stderr.write('-terms\toutput terms as\n')
	sys.stderr.write('\t\t0 - terms and weights (+ frequency if "-seq 2")\n')
	sys.stderr.write('\t\t1 - terms only\n')
	sys.exit(1)

def check_properties():		
	global term_number
	term_number=None
	global threshold
	threshold=None
	global ranking_method
	global ngram_length
	global output_file
	global position
	global min_frequency
	global seq
	seq=0
	global norm
	norm=0
	global terms
	terms=0
	# -prop
	if 'prop' in properties:
		if properties['prop']==[]:
			sys.stderr.write('Error: no argument given for property file (-prop)\n')
			print_help()
		import re
		line_re=re.compile('(.+?)=(.+)')
		try:
			properties_file=open(properties['prop'][-1])
		except:
			sys.stderr.write('Error: can not open property file (-prop): '+properties['prop'][-1]+'\n')
			print_help()
		i=0
		for line in properties_file:
			i+=1
			if line.strip().startswith('#'):
				continue
			result=line_re.search(line)
			if result is None:
				sys.stderr.write('Error in property file line '+str(i)+'\n'+repr(line)+'\n') 
				print_help()
			key=result.group(1).strip()
			if '"' in line:
				values=re.findall(r'"(.+?)"',result.group(2).strip())
			else:
				values=re.split(r'\s+',result.group(2).strip())
			if key not in definable_properties:
				sys.stderr.write('Error: unknown argument identifier '+key+' (property file)\n')
				print_help()
			properties[key]=values
	missing_properties=mandatory_properties.difference(mandatory_properties.intersection(properties))
	if len(missing_properties)>0:
		sys.stderr.write('Error: these mandatory properties are missing: '+', '.join(missing_properties)+'\n')
		print_help()

	# -n
	if 'n' in properties:
		if properties['n']==[]:
			sys.stderr.write('Error: no argument given for number of terms (-n)\n')
			print_help()		
		try:
			term_number=int(properties['n'][-1])
		except:
			sys.stderr.write('Error: wrong argument for number of terms (-n): '+properties['n'][-1]+'\n')
			print_help()
	# -t
	if 't' in properties:
		if properties['t']==[]:
			sys.stderr.write('Error: no argument given for threshold (-t)\n')
			print_help()
		try:
			threshold=float(properties['t'][-1])
		except:
			sys.stderr.write('Error: wrong argument for threshold (-t): '+properties['t'][-1]+'\n')
			print_help()
	# -m
	if properties['m']==[]:
		sys.stderr.write('Error: no argument given for n-gram ranking method (-m)\n')
		print_help()
	ranking_method=properties['m'][-1]
	if ranking_method not in ranking_methods:
		sys.stderr.write('Error: wrong argument for n-gram ranking method (-m): '+ranking_method+'\n')
		print_help()
	# -l
	if properties['l']==[]:
		sys.stderr.write('Error: no argument given for length of n-grams (-l)\n')
		print_help()
	try:
		ngram_length=int(properties['l'][-1])
		if ngram_length<1 or ngram_length>4:
			raise Exception
	except:
		sys.stderr.write('Error: wrong argument for length of n-grams (-l): '+properties['l'][-1]+'\n')
		print_help()
	#if ranking_method=='tfidf' and ngram_length!=1:
	#	sys.stderr.write('Error: tfidf ranking method applicable only to unigrams (-l 1)\n')
	#	print_help()
	if ngram_length==1 and 'idf' not in properties:
		sys.stderr.write('Error: idf file has to be defined for length of n-grams 1 (-l 1)\n')
		print_help()
	# -o
	if 'o' in properties:
		if properties['o']==[]:
			sys.stderr.write('Error: no argument given output file (-o)\n')
			print_help()
		try:
			output_file=open(properties['o'][-1],'w')
		except:
			sys.stderr.write('Error: can not write to output file '+properties['o'][-1]+'\n')
			print_help()	
	else:
		output_file=sys.stdout
	# -pos
	if 'pos' in properties:
		if len(properties['pos'])<3:
			sys.stderr.write('Error: wrong number of arguments given for position (-pos)\n')
			print_help()
		try:
			position=[int(e) for e in properties['pos'][-3:]]
			if len(set(position))!=3:
				raise Exception
		except:
			sys.stderr.write('Error: wrong arguments given for position (-pos): '+', '.join(properties['pos'][-3:])+'\n')
			print_help()
	else:
		position=range(3)
	# -min
	if 'min' in properties:
		if properties['min']==[]:
			sys.stderr.write('Error: no argument given for minimum frequency (-min)\n')
			print_help()
		try:
			min_frequency=int(properties['min'][-1])
		except:
			sys.stderr.write('Error: wrong argument given for minimum frequency (-min): '+properties['min'][-1]+'\n')
			print_help()
	# -idf
	if 'idf' in properties:
		if properties['idf']==[]:
			sys.stderr.write('Error: no argument given for idf file (-idf)\n')
			print_help()
	# -seq
	if 'seq' in properties:
		if properties['seq']==[]:
			sys.stderr.write('Error: no argument given for sequence output (-seq)\n')
			print_help()
		if properties['seq'][-1]!='0' and properties['seq'][-1]!='1' and properties['seq'][-1]!='2':
			sys.stderr.write('Error: wrong argument given for sequence output (-seq): '+properties['seq'][-1]+'\n')
			print_help()			
		seq=int(properties['seq'][-1])
	# -norm
	if 'norm' in properties:
		if properties['norm']==[]:
			sys.stderr.write('Error: no argument given for normalization (-norm)\n')
			print_help()
		try:
			norm=float(properties['norm'][-1])
		except:
			sys.stderr.write('Error: wrong argument given for normalization (-norm): '+properties['norm'][-1]+'\n')
			print_help()
	# -terms
	if 'terms' in properties:
		if properties['terms']==[]:
			sys.stderr.write('Error: no argument given for term output (-terms)\n')
			print_help()
		if properties['terms'][-1]!='0' and properties['terms'][-1]!='1':
			sys.stderr.write('Error: wrong argument given for term output (-terms): '+properties['terms'][-1]+'\n')
			print_help()			
		terms=int(properties['terms'][-1])

def read_phrase_configuration_file():
	global valid_phrases
	valid_phrases=[]
	global stop_phrase
	stop_phrase=[]
	global ngram_length
	if properties['p']==[]:
		sys.stderr.write('Error: no argument given for phrase configuration file (-p)\n')
		print_help()
	try:
		phrase_configuration_file=open(properties['p'][-1],'r')
	except:
		sys.stderr.write('Error: can not read phrase configuration file '+properties['p'][-1]+'\n')
		print_help()
	i=0
	for line in phrase_configuration_file:
		i+=1
		if line.strip().startswith('#'):
			continue
		if line.strip()=='':
			continue
		valid_phrase=line.strip().split('\t')
		try:
			if ngram_length!=len(valid_phrase):
				continue
			if 'STOP' in line:
				if stop_phrase!=[]:
					raise Exception
				for stop in valid_phrase:
					if stop not in ('!STOP','STOP','*'):
						raise Exception
				stop_phrase=valid_phrase
				continue
			valid_phrase=[re.compile(e) for e in valid_phrase]
		except:
			sys.stderr.write('Error in phrase configuration file line '+str(i)+'\n'+repr(line)+'\n')
			print_help()
		valid_phrases.append(valid_phrase)
	
def read_stopword_file():
	global stopwords
	stopwords=set()
	if 's' not in properties:
		return
	if properties['s']==[]:
		sys.stderr.write('Error: no argument given for stop-word file (-s)\n')
		print_help()
	try:
		stopwords=set([e.strip() for e in codecs.open(properties['s'][-1],'r','utf-8')])
	except:
		sys.stderr.write('Error: can not read stop-word file '+properties['s'][-1]+'\n')
		print_help()

def read_idf_file():
	if 'idf' not in properties:
		return
	global idf
	idf={}
	if properties['idf']==[]:
		sys.stderr.write('Error: no argument given for idf file (-idf)\n')
		print_help()
	try:
		idf=dict([(a,float(b)) for a,b in [e.split('\t') for e in codecs.open(properties['idf'][-1],'r','utf-8')]])
	except:
		sys.stderr.write('Error: can not read idf file '+properties['idf'][-1]+'\n')
		print_help()

def read_input_text():
	enamex=0
	numex=0
	timex=0
	if properties['i']==[]:
		sys.stderr.write('Error: no argument given for input file (-i)\n')
		print_help()
	path=properties['i'][-1]
	try:
		input_file=codecs.open(path,'r','utf-8')
	except:
		sys.stderr.write('Error: can not read input file '+path+'\n')
		print_help()
	i=0
	ngram=[None for e in range(ngram_length)]
	global ngram_frequency_distr
	ngram_frequency_distr={}
	global unigram_frequency_distr
	unigram_frequency_distr={}
	global lemma_token_frequency_distr
	lemma_token_frequency_distr={}
	global lemma_phrase_map
	lemma_phrase_map={}
	for line in input_file:
		if i==0:
			if line.startswith(u'\ufeff'):
				line=line[1:]
		i+=1
		split_line=line.strip().split('\t')
		if split_line==['']:
			continue
		if split_line[0][0]=='<':
			if split_line[0].startswith('<NUMEX'):
				numex+=1
			elif split_line[0].startswith('<ENAMEX'):
				enamex+=1
			elif split_line[0].startswith('<TIMEX'):
				timex+=1
			elif split_line[0].startswith('</NUMEX'):
				numex-=1
			elif split_line[0].startswith('</ENAMEX'):
				enamex-=1
			elif split_line[0].startswith('</TIMEX'):
				timex-=1
			else:
				continue
			ngram=[None for e in range(ngram_length)]
			if enamex<0 or numex<0 or timex<0:
				sys.stderr.write('Error: closing bracket without open on line '+str(i)+'\n'+repr(line)+'\n')
				sys.exit(1)
			continue
		if enamex!=0 or numex!=0 or timex!=0:
			continue
		try:
			token,pos,lemma=split_line[position[0]],split_line[position[1]],split_line[position[2]]
			token=token.lower()
			lemma=lemma.lower()
		except:
			sys.stderr.write('Error in input file line '+str(i)+'\n'+repr(line)+'\n')
			print_help()
		# actual stuff
		if ranking_method in ('dice','mi'):
			unigram_frequency_distr[lemma]=unigram_frequency_distr.get(lemma,0)+1
		ngram=ngram[1:]
		ngram.append((token,pos,lemma))
		try:
			tokens=tuple([e[0] for e in ngram])
			poses=tuple([e[1] for e in ngram])
			lemmas=tuple([e[2] for e in ngram])
		except:
			continue
		if ranking_method in ('ll','chisq','tscore'):
				for star_ngram in create_ngram_star(lemmas):
					ngram_frequency_distr[star_ngram]=ngram_frequency_distr.get(star_ngram,0)+1
		phrase=check_ngram_for_phrases(poses)
		if phrase!=None and check_ngram_for_stops(tokens):
			if lemmas not in lemma_phrase_map:
				lemma_phrase_map[lemmas]={}
			lemma_phrase_map[lemmas][phrase]=lemma_phrase_map[lemmas].get(phrase,0)+1
			if ranking_method in ('dice','mi','tfidf'):
				ngram_frequency_distr[lemmas]=ngram_frequency_distr.get(lemmas,0)+1
			if lemmas not in lemma_token_frequency_distr:
				lemma_token_frequency_distr[lemmas]={}
			lemma_token_frequency_distr[lemmas][tokens]=lemma_token_frequency_distr[lemmas].get(tokens,0)+1
	global results
	if ranking_method in ('dice','mi'):
		results=ranking_methods[ranking_method](ngram_frequency_distr,unigram_frequency_distr)
	elif ranking_method in ('ll','chisq','tscore','tfidf'):
		results=ranking_methods[ranking_method](ngram_frequency_distr)
	
def check_ngram_for_phrases(pos_ngram):
	for phrase in valid_phrases:
		valid=True
		for pos,regex in zip(pos_ngram,phrase):
			if pos is None:
				valid=False
				break
			if regex.match(pos) is None:
				valid=False
				break
		if valid:
			return ' '.join([e.pattern for e in phrase])

def check_ngram_for_stops(token_ngram):
	if stop_phrase==[]:
		return True
	for token,stop in zip(token_ngram,stop_phrase):
		if stop=='STOP' and token not in stopwords:
			return False
		elif stop=='!STOP' and token in stopwords:
			return False
	return True

def normalize_result():
	global results
	global norm
	if norm==0:
		norm=1
	values=[a for a,b in results]
	if len(values)==0:
		return
	min_value=min(values)
	max_value=max(values)
	range=float(max_value-min_value)
	for index,(value,ngram) in enumerate(results):
		try:
			results[index]=(norm*(value-min_value)/range,ngram)
		except ZeroDivisionError:
			results[index]=(norm,ngram)

def linearly_combine_with_idf():
	normalize_result()
	global results
	results=sorted([(value*0.5+avg_idf(ngram)*0.5, ngram) for value,ngram in results],reverse=True)

def output_result():
	i=0
	for value,ngram in results:
		if threshold is not None:
			if value<threshold:
				break
		if seq==0:
			output=' '.join(ngram).encode('utf-8')+'\t('+'|'.join([e[0] for e in sorted(lemma_phrase_map[ngram].items(),key=lambda x:-x[1])])+', '+str(ngram_frequency_distr[ngram])+')'
			if terms==0:
				output+='\t'+str(round(value,5))
			output_file.write(output+'\n')
		elif seq==1:
			output=' '.join(sorted(lemma_token_frequency_distr[ngram].items(),key=lambda x:x[1])[-1][0]).encode('utf-8')+'\t('+'|'.join([e[0] for e in sorted(lemma_phrase_map[ngram].items(),key=lambda x:-x[1])])+', '+str(ngram_frequency_distr[ngram])+')'
			if terms==0:
				output+='\t'+str(round(value,5))
			output_file.write(output+'\n')
		elif seq==2:
			output=' '.join(ngram).encode('utf-8')+'\t'+' '.join(sorted(lemma_token_frequency_distr[ngram].items(),key=lambda x:x[1])[-1][0]).encode('utf-8')+'\t('+'|'.join([e[0] for e in sorted(lemma_phrase_map[ngram].items(),key=lambda x:-x[1])])+', '+str(ngram_frequency_distr[ngram])+')'
			if terms==0:
				output+='\t'+str(round(value,5))
			output_file.write(output+'\n')
		else:
			for token_sequence,frequency in lemma_token_frequency_distr[ngram].iteritems():
				output=' '.join(token_sequence).encode('utf-8')+'\t('+'|'.join([e[0] for e in sorted(lemma_phrase_map[ngram].items(),key=lambda x:-x[1])])+', '+str(ngram_frequency_distr[ngram])+')'
				if terms==0:
					output+='\t'+str(frequency)+'\t'+str(round(value,5))
				output_file.write(output+'\n')
		i+=1
		if term_number is not None:
			if i>=term_number:
				break

if __name__=='__main__':
	parse_arguments()
	check_properties()
	read_phrase_configuration_file()
	read_stopword_file()
	read_idf_file()
	read_input_text()
	if ranking_method!='tfidf' and 'idf' in vars():
		linearly_combine_with_idf()
	if norm!=0:
		normalize_result()
	output_result()
