source: trunk/CrypPlugins/CostFunction/CostFunction.cs @ 1864

Last change on this file since 1864 was 1864, checked in by malischewski, 11 years ago

further modifications for testing

File size: 27.0 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections.Generic;
19using System.Collections;
20using System.Linq;
21using System.Text;
22using Cryptool.PluginBase.Cryptography;
23using Cryptool.PluginBase;
24using Cryptool.PluginBase.Miscellaneous;
25using Cryptool.PluginBase.Analysis;
26using System.ComponentModel;
27using Cryptool.PluginBase.Control;
28using System.IO;
29using System.Text.RegularExpressions;
30using System.Threading;
31using System.Reflection;
32namespace Cryptool.Plugins.CostFunction
33{
34    [Author("Nils Kopal, Simon Malischewski", "Nils.Kopal@cryptool.org , malischewski@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
35    [PluginInfo(false, "CostFunction", "CostFunction", "CostFunction/DetailedDescription/Description.xaml", "CostFunction/icon.png")]
36    public class CostFunction : IAnalysisMisc
37    {
38        #region private variables
39        private CostFunctionSettings settings = new CostFunctionSettings();
40        private byte[] inputText = null;
41        private byte[] outputText = null;
42        private double value = 0.0;
43        private Boolean stopped = true;
44        private IControlCost controlSlave;
45        private String bigramInput;
46        private double[,] bigramMatrix;
47        private IDictionary<string, double[]> corpusGrams;
48
49        private IDictionary<string, double[]> corpusBigrams; // Used for Weighted Bigrams/Trigrams Cost function
50        private IDictionary<string, double[]> corpusTrigrams;
51
52        //Fitness Weight Table for Weighted Bigrams/Trigrams
53        private IDictionary<string, double> fwt = new Dictionary<string, double>();
54
55        //Weights
56        private double beta = 1.0;
57        private double gamma = 1.0;
58
59       
60        private DataManager dataMgr = new DataManager(Path.GetDirectoryName(Assembly.GetExecutingAssembly().Location)); 
61        private const string DATATYPE = "transposition";
62
63        private IDictionary<String, DataFileMetaInfo> txtList;
64        private IDictionary<int, IDictionary<string, double[]>> statistics;
65
66        #endregion
67        #region internal constants
68        internal const int ABSOLUTE = 0;
69        internal const int PERCENTAGED = 1;
70        internal const int LOG2 = 2;
71        internal const int SINKOV = 3;
72        #endregion
73        #region CostFunctionInOut
74
75        [PropertyInfo(Direction.InputData, "Text Input", "Input your Text here", "", DisplayLevel.Beginner)]
76        public byte[] InputText
77        {
78            get
79            {
80                return inputText;
81            }
82            set
83            {
84                this.inputText = value;
85                OnPropertyChanged("InputText");
86            }
87        }
88        #region testing
89        public void changeFunctionType(int type)
90        {
91            this.settings.changeFunctionType(type);
92        }
93
94        public void setDataPath(string path)
95        {
96            this.testing = true;
97            this.settings.customFilePath = path;
98        }
99        public void setRegEx(string regex)
100        {
101            this.settings.RegEx = regex;
102        }
103        #endregion
104
105        [PropertyInfo(Direction.OutputData, "Text Output", "Your Text will be send here", "", DisplayLevel.Beginner)]
106        public byte[] OutputText
107        {
108            get
109            {
110                return outputText;
111            }
112            set
113            {
114                this.outputText = value;
115                OnPropertyChanged("OutputText");
116            }
117        }
118
119        [PropertyInfo(Direction.OutputData, "Value", "The value of the function will be send here", "", DisplayLevel.Beginner)]
120        public double Value
121        {
122            get
123            {
124                return value;
125            }
126            set
127            {
128                this.value = value;
129                OnPropertyChanged("Value");
130            }
131        }
132
133        [PropertyInfo(Direction.ControlSlave, "SDES Slave", "Direct access to SDES.", "", DisplayLevel.Beginner)]
134        public IControlCost ControlSlave
135        {
136            get
137            {
138                if (controlSlave == null)
139                    controlSlave = new CostFunctionControl(this);
140                return controlSlave;
141            }
142        }
143
144        #endregion
145
146        #region IPlugin Members
147
148        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
149        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
150
151
152        public ISettings Settings
153        {
154            get { return this.settings; }
155            set { this.settings = (CostFunctionSettings)value; }
156        }
157
158        public System.Windows.Controls.UserControl Presentation
159        {
160            get { return null; }
161        }
162
163        public System.Windows.Controls.UserControl QuickWatchPresentation
164        {
165            get { return null; }
166        }
167
168        public void PreExecution()
169        {
170            this.stopped = false;
171        }
172
173        public void Execute()
174        {
175            if (this.InputText is Object && this.stopped == false)
176            {
177                int bytesToUse = 0;
178                try
179                {
180                    bytesToUse = int.Parse(settings.BytesToUse);
181                }
182                catch (Exception ex)
183                {
184                    GuiLogMessage("Entered bytesToUse is not an integer: " + ex.Message, NotificationLevel.Error);
185                    return;
186                }
187
188                if (bytesToUse > this.InputText.Length)
189                {
190                    bytesToUse = 0;
191                }
192
193                byte[] array;
194
195                if (bytesToUse > 0)
196                {
197                    //Create a new Array of size of bytesToUse if needed
198                    array = new byte[bytesToUse];
199                    for (int i = 0; i < bytesToUse && i < this.InputText.Length; i++)
200                    {
201                        array[i] = InputText[i];
202                    }
203                }
204                else
205                {
206                    array = this.InputText;
207                }
208
209                ProgressChanged(0.5, 1);
210                bigramInput = ByteArrayToString(array);
211                switch (settings.FunctionType)
212                {
213
214                    case 0: // Index of Coincedence
215                        this.Value = calculateIndexOfCoincidence(array);
216                        break;
217
218                    case 1: // Entropy
219                        this.Value = calculateEntropy(array);
220                        break;
221
222                    case 2: // Log 2 Bigrams
223                        this.Value = calculateNGrams(bigramInput, 2, 2,false);
224                        break;
225
226                    case 3: // sinkov Bigrams
227                        this.Value = calculateNGrams(bigramInput, 2, 3,false);
228                        break;
229                    case 4: //percentaged Bigrams
230                        this.Value = calculateNGrams(bigramInput, 2, 1,false);
231                        break;
232                    case 5: //regular expressions
233                        this.Value = regex(bigramInput);
234                        break;
235                    case 6: // Weighted Bigrams/Trigrams (used by genetic algorithm in transposition analyser)
236                        this.Value = calculateWeighted(bigramInput);
237                        break;
238
239                    default:
240                        this.Value = -1;
241                        break;
242                }//end switch               
243
244                this.OutputText = this.InputText;
245                ProgressChanged(1, 1);
246
247            }//end if
248
249        }
250
251
252
253        public void PostExecution()
254        {
255            this.stopped = true;
256        }
257
258        public void Pause()
259        {
260
261        }
262
263        public void Stop()
264        {
265            this.stopped = false;
266        }
267
268        public void Initialize()
269        {
270
271        }
272
273        public void Dispose()
274        {
275
276        }
277
278        #endregion
279
280        #region INotifyPropertyChanged Members
281
282        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
283
284        public void OnPropertyChanged(string name)
285        {
286            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
287        }
288
289        private void ProgressChanged(double value, double max)
290        {
291            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
292        }
293
294        public void GuiLogMessage(string p, NotificationLevel notificationLevel)
295        {
296            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
297        }
298
299        #endregion
300
301        #region IPlugin Members
302
303        public event StatusChangedEventHandler OnPluginStatusChanged;
304
305        #endregion
306
307        #region private methods
308
309        // Reads data directory, passes filepaths to parser
310        private void fillfwt() {
311             txtList = dataMgr.LoadDirectory(DATATYPE);
312
313
314             switch (this.settings.weighttable)
315             {
316                 case 0:
317                     parseCSV(txtList["fwtmatthews"].DataFile.FullName);
318                     break;
319                 case 1:
320                     parseCSV(txtList["fwttoemeharumugam"].DataFile.FullName);
321                     break;
322                 case 2:
323                     parseCSV(this.settings.customfwtpath);
324                     break;
325             }
326
327
328             
329        }
330        // simple "parser" for CSV files
331        private void parseCSV(string path)
332        {
333            using (StreamReader readFile = new StreamReader(path))
334            {
335                string line;
336                string[] row;
337
338                while ((line = readFile.ReadLine()) != null)
339                {
340
341                    row = line.Split(';');
342                    if (row.Length == 2)
343                    {
344                        fwt.Add(row[0], Double.Parse(row[1]));
345                    }
346                }
347            }
348           
349        }
350
351        private void weights(string ngram, int ngramlength)
352        {
353            if (fwt.TryGetValue(ngram, out value) && ngramlength == 2)
354            {
355                beta += value;
356            }
357
358            if (fwt.TryGetValue(ngram, out value) && ngramlength == 3)
359            {
360                gamma += value;
361            }
362
363
364        }
365
366        //public double contains(string input)
367        //{
368        //    if (settings.Contains == null)
369        //    {
370        //        GuiLogMessage("There is no text to be searched for. Please insert text in the 'Contains text / Regular Expression' - Textarea", NotificationLevel.Error);
371        //        return new Double();
372        //    }
373
374        //    if (input.Contains(settings.Contains))
375        //    {
376        //        return 1.0;
377        //    }
378        //    return -1.0;
379        //}
380        public double calculateWeighted(string input)
381        {
382           
383            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
384
385            if (fwt == null) { fillfwt(); } 
386            if (corpusBigrams == null)
387            {
388                if (corpusTrigrams == null)
389                {
390
391                    corpusBigrams = GetStatistics(2); // Get Known Language statistics for Bigrams
392                    corpusTrigrams = GetStatistics(3); // and Trigrams
393                }
394
395            }
396            input = input.ToUpper();
397
398            double bigramscore = calculateNGrams(input, 2, 3, true); // Sinkov
399            double trigramscore = calculateNGrams(input, 3, 3, true);
400         
401            return (beta * bigramscore) + (gamma * trigramscore);
402           
403        }
404
405        public double regex(string input)
406        {
407            if (settings.RegEx == null)
408            {
409                GuiLogMessage("There is no Regular Expression to be searched for. Please insert regex in the 'Regular Expression' - Textarea", NotificationLevel.Error);
410                return new Double();
411            }
412            try
413            {
414                Match match = Regex.Match(input, settings.RegEx);
415                if (match.Success)
416                {
417                    return 1.0;
418                }
419                else
420                {
421                    return -1.0;
422                }
423            }
424            catch (Exception e)
425            {
426                GuiLogMessage(e.Message, NotificationLevel.Error);
427                return -1.0;
428            }
429
430        }
431
432
433        /// <summary>
434        /// Calculates the Index of Coincidence multiplied with 100 of
435        /// a given byte array
436        ///
437        /// for example a German text has about 7.62
438        ///           an English text has about 6.61
439        /// </summary>
440        /// <param name="text">text to use</param>
441        /// <returns>Index of Coincidence</returns>
442        public double calculateIndexOfCoincidence(byte[] text)
443        {
444            return calculateIndexOfCoincidence(text, text.Length);
445        }
446
447        /// <summary>
448        /// Calculates the Index of Coincidence multiplied with 100 of
449        /// a given byte array
450        ///
451        /// for example a German text has about 7.62
452        ///           an English text has about 6.61
453        /// </summary>
454        /// <param name="text">text to use</param>
455        /// <param name="text">bytesToUse</param>
456        /// <returns>Index of Coincidence</returns>
457        public double calculateIndexOfCoincidence(byte[] text, int bytesToUse)
458        {
459            if (bytesToUse > text.Length)
460                bytesToUse = text.Length;
461
462            double[] n = new double[256];
463            //count all ASCII symbols
464            int counter = 0;
465            foreach (byte b in text)
466            {
467                n[b]++;
468                counter++;
469                if (counter == bytesToUse)
470                    break;
471            }
472
473            double coindex = 0;
474            //sum them
475            for (int i = 0; i < n.Length; i++)
476            {
477                coindex = coindex + n[i] * (n[i] - 1);
478            }
479
480            coindex = coindex / (bytesToUse);
481            coindex = coindex / (bytesToUse - 1);
482
483            return coindex * 100;
484
485        }//end calculateIndexOfCoincidence
486
487
488        private int lastUsedSize = -1;
489        private double[] xlogx;
490        private Mutex prepareMutex = new Mutex();
491        private bool testing = false;
492
493        private void prepareEntropy(int size)
494        {
495            xlogx = new double[size + 1];
496            //precomputations for fast entropy calculation     
497            xlogx[0] = 0.0;
498            for (int i = 1; i <= size; i++)
499                xlogx[i] = -1.0 * i * Math.Log(i / (double)size) / Math.Log(2.0);
500        }
501
502        /// <summary>
503        /// Calculates the Entropy of a given byte array
504        /// for example a German text has about 4.0629
505        /// </summary>
506        /// <param name="text">text to use</param>
507        /// <returns>Entropy</returns>
508        public double calculateEntropy(byte[] text)
509        {
510            return calculateEntropy(text, text.Length);
511        }
512
513        /// <summary>
514        /// Calculates the Entropy of a given byte array
515        /// for example a German text has about 4.0629
516        /// </summary>
517        /// <param name="text">text to use</param>
518        /// <returns>Entropy</returns>
519        public double calculateEntropy(byte[] text, int bytesToUse)
520        {
521            return NativeCryptography.Crypto.calculateEntropy(text, bytesToUse);
522            if (bytesToUse > text.Length)
523           
524                bytesToUse = text.Length;
525           
526            if (lastUsedSize != bytesToUse)
527            {
528                try
529                {
530                    prepareMutex.WaitOne();
531                    if (lastUsedSize != bytesToUse)
532                    {
533                        prepareEntropy(bytesToUse);
534                        lastUsedSize = bytesToUse;
535                    }
536                }
537                finally
538                {
539                    prepareMutex.ReleaseMutex();
540                }
541            }
542
543            int[] n = new int[256];
544            //count all ASCII symbols
545            for (int counter = 0; counter < bytesToUse; counter++)
546            {
547                n[text[counter]]++;
548            }
549
550            double entropy = 0;
551            //calculate probabilities and sum entropy
552            for (int i = 0; i < 256; i++)
553                entropy += xlogx[n[i]];
554
555            return entropy / (double)bytesToUse;
556
557        }//end calculateEntropy
558
559        /// <summary>
560        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
561        /// Case is insensitive.
562        /// </summary>
563        /// <param name="input">The text to be scored</param>
564        /// <param name="length">n-gram length</param>
565        /// <returns>The trigram score result</returns>
566        public double calculateNGrams(string input, int length, int valueSelection, bool weighted)
567        {
568
569            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
570            double score = 0;
571            if (corpusBigrams == null && length == 2)
572            { corpusBigrams = GetStatistics(length); }
573
574            if (corpusTrigrams == null && length == 3)
575            { corpusTrigrams = GetStatistics(length); }
576            input = input.ToUpper();
577            // FIXME: case handling?
578
579            HashSet<string> inputGrams = new HashSet<string>();
580
581            foreach (string g in GramTokenizer.tokenize(input, length, false))
582            {
583                // ensure each n-gram is counted only once
584                if (inputGrams.Add(g))
585                {
586                    if (corpusBigrams.ContainsKey(g) && length == 2 )
587                    {
588                        score += corpusBigrams[g][valueSelection];
589                        if (weighted) { weights(g, 2); }
590                    }
591                    if (length == 3 )
592                    {
593                        if (corpusTrigrams.ContainsKey(g))
594                        {
595                            score += corpusTrigrams[g][valueSelection];
596                            if (weighted) { weights(g, 3); }
597                        }
598                    }
599                }
600            }
601
602            return score;
603        }
604        public IDictionary<string, double[]> GetStatistics(int gramLength)
605        {
606            // FIXME: inputTriGrams is not being used!
607
608            // FIXME: implement exception handling
609            if (!statistics.ContainsKey(gramLength))
610            {
611                //GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
612                statistics[gramLength] = LoadDefaultStatistics(gramLength);
613            }
614
615            return statistics[gramLength];
616        }
617
618        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
619        {
620           
621            txtList = dataMgr.LoadDirectory(DATATYPE);
622            if (testing) { return calculateAbsolutes(this.settings.customFilePath, length); }
623            switch (this.settings.StatisticsCorpus)
624            {
625                case 0:
626                    return calculateAbsolutes(txtList["statisticscorpusde"].DataFile.FullName, length);
627                   
628                case 1:
629                    return calculateAbsolutes(txtList["statisticscorpusen"].DataFile.FullName, length);
630                case 2:
631                    return calculateAbsolutes(this.settings.customFilePath, length);
632                //to prevent a poss. initial-err
633                //default:
634                //    return calculateAbsolutes(txtList["statisticscorpusen"].DataFile.FullName, length);
635
636            }
637            return calculateAbsolutes(txtList["statisticscorpusde"].DataFile.FullName, length); //default
638           
639        }
640
641        private IDictionary<string, double[]> calculateAbsolutes(String path, int length)
642        {
643
644
645            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
646            int checkLength;
647            StreamReader reader = new StreamReader(path);
648            String text = reader.ReadToEnd();
649
650            text.ToUpper();
651            text = Regex.Replace(text, "[^A-Z]*", "");
652
653            if (length == 2)
654            {
655                checkLength = text.Length - 1;
656            }
657            else
658            {
659                checkLength = text.Length - 2;
660            }
661            for (int i = 0; i < checkLength; i++)
662            {
663                char a = text[i];
664                char b = text[i + 1];
665                String key;
666                if (length == 3) // Trigrams
667                {
668                    char c = text[i + 2];
669                    key = a.ToString();
670                    key = key + b.ToString();
671                    key = key + c.ToString();
672                }
673                else // Bigrams
674                {
675                    key = a.ToString();
676                    key = key + b.ToString();
677                }
678
679                if (!grams.ContainsKey(key))
680                {
681                    grams.Add(key, new double[] { 1, 0, 0, 0}); 
682                }
683                else
684                {
685                    grams[key][0] = grams[key][0] + 1.0;
686                }
687            }
688
689            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
690            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
691
692            // calculate scaled values
693            foreach (double[] g in grams.Values)
694            {
695                g[PERCENTAGED] = g[ABSOLUTE] / sum;
696                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
697                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
698            }
699
700
701
702            return grams;
703        }
704
705        public string ByteArrayToString(byte[] arr)
706        {
707            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
708            return enc.GetString(arr);
709        }
710
711
712        #endregion
713
714
715    }
716
717    #region slave
718
719    public class CostFunctionControl : IControlCost
720    {
721        public event IControlStatusChangedEventHandler OnStatusChanged;
722        #region IControlCost Members
723
724        private CostFunction plugin;
725
726        #endregion
727
728        /// <summary>
729        /// Constructor
730        /// </summary>
731        /// <param name="plugin"></param>
732        public CostFunctionControl(CostFunction plugin)
733        {
734            this.plugin = plugin;
735        }
736
737        public int getBytesToUse()
738        {
739            try
740            {
741                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
742            }
743            catch (Exception ex)
744            {
745                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
746            }
747        }
748
749        /// <summary>
750        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
751        /// </summary>
752        /// <returns>RelationOperator</returns>
753        public RelationOperator getRelationOperator()
754        {
755            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
756            {
757                case 0: //Index of coincidence
758                    return RelationOperator.LargerThen;
759                case 1: //Entropy
760                    return RelationOperator.LessThen;
761                case 2: // Bigrams: log 2
762                    return RelationOperator.LessThen;
763                case 3: // Sinkov
764                    return RelationOperator.LargerThen;
765                case 4: // percentage
766                    return RelationOperator.LargerThen;
767                case 5: // Regular Expression
768                    return RelationOperator.LargerThen;
769                case 6: // Weighted Bigrams/Trigrams
770                    return RelationOperator.LargerThen;
771
772                default:
773                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
774            }//end switch
775        }//end getRelationOperator
776
777        /// <summary>
778        /// Calculates the cost function of the given text
779        ///
780        /// Cost function can be set by CostFunctionSettings
781        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
782        /// If bytesToUse is set to 0 it uses the whole text
783        ///
784        /// </summary>
785        /// <param name="text"></param>
786        /// <returns>cost</returns>
787        public double calculateCost(byte[] text)
788        {
789            int bytesToUse = 0;
790            try
791            {
792                bytesToUse = ((CostFunctionSettings)this.plugin.Settings).BytesToUseInteger;
793            }
794            catch (Exception ex)
795            {
796                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
797            }
798
799            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
800            {
801                case 0: //Index of coincidence
802                    return plugin.calculateIndexOfCoincidence(text, bytesToUse);
803                case 1: //Entropy
804                    return plugin.calculateEntropy(text, bytesToUse);
805                case 2: // Bigrams: log 2
806                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 2, false);
807                case 3: // Bigrams: Sinkov
808                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 3, false);
809                case 4: // Bigrams: Percentaged
810                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 1, false);
811                case 5: // regular expression
812                    return plugin.regex(plugin.ByteArrayToString(text));
813                case 6:
814                    return plugin.calculateWeighted(plugin.ByteArrayToString(text));
815                default:
816                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
817            }//end switch
818        }
819
820
821    #endregion
822    }
823
824}
825
Note: See TracBrowser for help on using the repository browser.