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

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

Entropy switch visibility bug fix

File size: 27.5 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        /* obsolete
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               
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            switch (this.settings.entropyselect)
522            {
523                case 0:
524                    return NativeCryptography.Crypto.calculateEntropy(text, bytesToUse);
525                case 1:
526                    if (bytesToUse > text.Length)
527
528                        bytesToUse = text.Length;
529
530                    if (lastUsedSize != bytesToUse)
531                    {
532                        try
533                        {
534                            prepareMutex.WaitOne();
535                            if (lastUsedSize != bytesToUse)
536                            {
537                                prepareEntropy(bytesToUse);
538                                lastUsedSize = bytesToUse;
539                            }
540                        }
541                        finally
542                        {
543                            prepareMutex.ReleaseMutex();
544                        }
545                    }
546
547                    int[] n = new int[256];
548                    //count all ASCII symbols
549                    for (int counter = 0; counter < bytesToUse; counter++)
550                    {
551                        n[text[counter]]++;
552                    }
553
554                    double entropy = 0;
555                    //calculate probabilities and sum entropy
556                    for (int i = 0; i < 256; i++)
557                        entropy += xlogx[n[i]];
558
559                    return entropy / (double)bytesToUse;
560                default:
561                    return NativeCryptography.Crypto.calculateEntropy(text, bytesToUse);
562            }
563        }//end calculateEntropy
564
565        /// <summary>
566        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
567        /// Case is insensitive.
568        /// </summary>
569        /// <param name="input">The text to be scored</param>
570        /// <param name="length">n-gram length</param>
571        /// <returns>The trigram score result</returns>
572        public double calculateNGrams(string input, int length, int valueSelection, bool weighted)
573        {
574
575            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
576            double score = 0;
577            if (corpusBigrams == null && length == 2)
578            { corpusBigrams = GetStatistics(length); }
579
580            if (corpusTrigrams == null && length == 3)
581            { corpusTrigrams = GetStatistics(length); }
582            input = input.ToUpper();
583            // FIXME: case handling?
584
585            HashSet<string> inputGrams = new HashSet<string>();
586
587            foreach (string g in GramTokenizer.tokenize(input, length, false))
588            {
589                // ensure each n-gram is counted only once
590                if (inputGrams.Add(g))
591                {
592                    if (corpusBigrams.ContainsKey(g) && length == 2 )
593                    {
594                        score += corpusBigrams[g][valueSelection];
595                        if (weighted) { weights(g, 2); }
596                    }
597                    if (length == 3 )
598                    {
599                        if (corpusTrigrams.ContainsKey(g))
600                        {
601                            score += corpusTrigrams[g][valueSelection];
602                            if (weighted) { weights(g, 3); }
603                        }
604                    }
605                }
606            }
607
608            return score;
609        }
610        public IDictionary<string, double[]> GetStatistics(int gramLength)
611        {
612            // FIXME: inputTriGrams is not being used!
613
614            // FIXME: implement exception handling
615            if (!statistics.ContainsKey(gramLength))
616            {
617                //GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
618                statistics[gramLength] = LoadDefaultStatistics(gramLength);
619            }
620
621            return statistics[gramLength];
622        }
623
624        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
625        {
626           
627            txtList = dataMgr.LoadDirectory(DATATYPE);
628            if (testing) { return calculateAbsolutes(this.settings.customFilePath, length); }
629            switch (this.settings.StatisticsCorpus)
630            {
631                case 0:
632                    return calculateAbsolutes(txtList["statisticscorpusde"].DataFile.FullName, length);
633                   
634                case 1:
635                    return calculateAbsolutes(txtList["statisticscorpusen"].DataFile.FullName, length);
636                case 2:
637                    return calculateAbsolutes(this.settings.customFilePath, length);
638                //to prevent a poss. initial-err
639                //default:
640                //    return calculateAbsolutes(txtList["statisticscorpusen"].DataFile.FullName, length);
641
642            }
643            return calculateAbsolutes(txtList["statisticscorpusde"].DataFile.FullName, length); //default
644           
645        }
646
647        private IDictionary<string, double[]> calculateAbsolutes(String path, int length)
648        {
649
650
651            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
652            int checkLength;
653            StreamReader reader = new StreamReader(path);
654            String text = reader.ReadToEnd();
655
656            text.ToUpper();
657            text = Regex.Replace(text, "[^A-Z]*", "");
658
659            if (length == 2)
660            {
661                checkLength = text.Length - 1;
662            }
663            else
664            {
665                checkLength = text.Length - 2;
666            }
667            for (int i = 0; i < checkLength; i++)
668            {
669                char a = text[i];
670                char b = text[i + 1];
671                String key;
672                if (length == 3) // Trigrams
673                {
674                    char c = text[i + 2];
675                    key = a.ToString();
676                    key = key + b.ToString();
677                    key = key + c.ToString();
678                }
679                else // Bigrams
680                {
681                    key = a.ToString();
682                    key = key + b.ToString();
683                }
684
685                if (!grams.ContainsKey(key))
686                {
687                    grams.Add(key, new double[] { 1, 0, 0, 0}); 
688                }
689                else
690                {
691                    grams[key][0] = grams[key][0] + 1.0;
692                }
693            }
694
695            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
696            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
697
698            // calculate scaled values
699            foreach (double[] g in grams.Values)
700            {
701                g[PERCENTAGED] = g[ABSOLUTE] / sum;
702                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
703                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
704            }
705
706
707
708            return grams;
709        }
710
711        public string ByteArrayToString(byte[] arr)
712        {
713            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
714            return enc.GetString(arr);
715        }
716
717
718        #endregion
719
720
721    }
722
723    #region slave
724
725    public class CostFunctionControl : IControlCost
726    {
727        public event IControlStatusChangedEventHandler OnStatusChanged;
728        #region IControlCost Members
729
730        private CostFunction plugin;
731
732        #endregion
733
734        /// <summary>
735        /// Constructor
736        /// </summary>
737        /// <param name="plugin"></param>
738        public CostFunctionControl(CostFunction plugin)
739        {
740            this.plugin = plugin;
741        }
742
743        public int getBytesToUse()
744        {
745            try
746            {
747                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
748            }
749            catch (Exception ex)
750            {
751                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
752            }
753        }
754
755        /// <summary>
756        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
757        /// </summary>
758        /// <returns>RelationOperator</returns>
759        public RelationOperator getRelationOperator()
760        {
761            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
762            {
763                case 0: //Index of coincidence
764                    return RelationOperator.LargerThen;
765                case 1: //Entropy
766                    return RelationOperator.LessThen;
767                case 2: // Bigrams: log 2
768                    return RelationOperator.LessThen;
769                case 3: // Sinkov
770                    return RelationOperator.LargerThen;
771                case 4: // percentage
772                    return RelationOperator.LargerThen;
773                case 5: // Regular Expression
774                    return RelationOperator.LargerThen;
775                case 6: // Weighted Bigrams/Trigrams
776                    return RelationOperator.LargerThen;
777
778                default:
779                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
780            }//end switch
781        }//end getRelationOperator
782
783        /// <summary>
784        /// Calculates the cost function of the given text
785        ///
786        /// Cost function can be set by CostFunctionSettings
787        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
788        /// If bytesToUse is set to 0 it uses the whole text
789        ///
790        /// </summary>
791        /// <param name="text"></param>
792        /// <returns>cost</returns>
793        public double calculateCost(byte[] text)
794        {
795            int bytesToUse = 0;
796            try
797            {
798                bytesToUse = ((CostFunctionSettings)this.plugin.Settings).BytesToUseInteger;
799            }
800            catch (Exception ex)
801            {
802                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
803            }
804
805            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
806            {
807                case 0: //Index of coincidence
808                    return plugin.calculateIndexOfCoincidence(text, bytesToUse);
809                case 1: //Entropy
810                    return plugin.calculateEntropy(text, bytesToUse);
811                case 2: // Bigrams: log 2
812                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 2, false);
813                case 3: // Bigrams: Sinkov
814                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 3, false);
815                case 4: // Bigrams: Percentaged
816                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 1, false);
817                case 5: // regular expression
818                    return plugin.regex(plugin.ByteArrayToString(text));
819                case 6:
820                    return plugin.calculateWeighted(plugin.ByteArrayToString(text));
821                default:
822                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
823            }//end switch
824        }
825
826
827    #endregion
828    }
829
830}
831
Note: See TracBrowser for help on using the repository browser.